Wannafly14挑战赛 C（tarjan缩点）题解-白红宇

Wannafly14挑战赛 C（tarjan缩点）题解

阅读量：6731 次

发布时间：2019-06-25

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

题目：

思路：这道题有点像

先缩点，缩完之后判断一下整个强连通分量入度是不是0，如果是的话向ans压入该强连通分量最小的那个值。最后排序一下ans输出就行了。

思路一下就想到了，就是写的有点迷，WA了好几发，加点注释...

炜神tql...果然我还是菜鸡，水题切的贼慢orz

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
              #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #define ll long long const int N=1e5+5;const ll INF=1e5+5;using namespace std;int n,m,cnt;map
                  
                    vis;set
                   
                     o;vector
                    
                      g[N],check,ans,in[N];    //in记录的是指向i的点，在后面用来判断stack
                     
                       s;int dfn[N],low[N];void tarjan(int x){ dfn[x]=low[x]=++cnt; s.push(x); vis[x]=1; for(int i=0;i