loj 1168(Tarjan应用)-白红宇

loj 1168(Tarjan应用)

阅读量：7023 次

发布时间：2019-06-28

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

题目链接：

思路：一开始把题意理解错了，还以为是简单路径，然后仔细一看发现是一条路径，意思就是说从起点出发，把所有的点走一遍，于是就要考虑强连通分量，因为对于同一个强连通分量的点是相互可达的，于是我们可以先缩点，建新图，统计新图中顶点的入度与出度的关系，判断即可。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #include
               10 #include
               
                 11 #include
                
                  12 #include
                 
                   13 #include
                  
                    14 using namespace std; 15 #define MAXN 1111 16 #define inf 1<<30 17 #define INF 1LL<<60 18 #define FILL(a,b) memset(a,b,sizeof(a)) 19 typedef long long ll; 20 typedef unsigned long long llu; 21 typedef pair
                   
                    PP; 22 template
                    
                      inline T Get_MIN(const T &a,const T &b){ return a < b ? a : b; } 23 template
                     
                       inline T Get_MAX(const T &a,const T &b){ return a > b ? a : b; } 24 template
                      
                        inline T ABS(const T &a){ return a < 0 ? -a : a; } 25 26 int n,m,k; 27 bool vis[MAXN]; 28 vector
                       
                        
                          >g,num; 29 map
                         
                          ID; 30 31 int low[MAXN],dfn[MAXN],color[MAXN]; 32 int scc_count,cnt; 33 bool mark[MAXN]; 34 stack
                          
                           S; 35 36 void Tarjan(int u) 37 { 38 low[u]=dfn[u]=++cnt; 39 mark[u]=true; 40 S.push(u); 41 for(int i=0;i

View Code

转载地址：http://knsxl.baihongyu.com/

你可能感兴趣的文章