uva 11504（强连通分支）-白红宇

uva 11504（强连通分支）

阅读量：6000 次

发布时间：2019-06-20

本文共 1441 字，大约阅读时间需要 4 分钟。

题意：有一些骨牌，告诉你一些关系a->b表示a倒了b也会倒。然后问你最少要推到几个才能使所有的骨牌都倒下。

思路：这道题其实就是用的强连通分支的kosaraju算法。其实在了解了这个算法之后我们不妨来想想是怎么样的一个逻辑关系。第一遍dfs我们先得到了在vs数组中的拓扑关系。到了第二遍，我们就从拓扑序列高的先开始dfs（可以直观的了解到只要拓扑序列高的倒下了，那么拓扑序列低的必定倒下了）所以我们得到的dfs次数即为答案了。

代码如下：

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-01-28 22:16 5  * Filename     : uva_11504.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 100000+10;34 vector
                      
                        vs, Map[LEN];35 int vis[LEN], n, m, scct[LEN];36 37 void dfs(int v){38 vis[v] = 1;39 for(int i=0; i
                       
                        =0; i--){60 if(!vis[vs[i]])rdfs(vs[i], f++);61 }62 return f;63 }64 65 int main()66 {67 // freopen("in.txt", "r", stdin);68 69 int T, a, b;70 scanf("%d", &T);71 while(T--){72 for(int i=0; i

View Code

转载于:https://www.cnblogs.com/shu-xiaohao/p/3536167.html

你可能感兴趣的文章

[游戏开发]关于手游客户端网络带宽压力的一点思考