强联通入门

0x01:基本概念

联通:无向图中,从任一点(i)可以到达图中的任意点(j)

强联通:有向图中,从任一(i)可以到达图中的任意点(j)

弱联通:把有向图看成一个无向图时,它是一个联通图

强联通分量:整个图不是强联通的,但是中间一部分是强联通的,这些强联通的部分就叫做强联通分量

0x02:强联通分量模板：(大佬的课：here)

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 typedef long double ld;
 5 #define endl '
'
 6 const int inf=0x3f3f3f3f;
 7 const int maxn=1e4+10;
 8 const int maxm=1e5+10;
 9 
10 /*****************************************************
11     强联通分量 strongly connected component
12 ******************************************************/
13 
14 /******************************************************
15     给一个有向图,输出它的每一个强联通分量
16 *******************************************************/
17 
18 struct node{
19     int to,nxt;
20 }e[maxm];
21 
22 int head[maxn],tot;
23 int dfn[maxn],low[maxn],cnt;    //cnt为时间戳
24 int _stack[maxn],top;
25 bool instack[maxn];
26 int belong[maxn],scnt;
27 int n,m;
28 
29 void init(){
30     memset(head,-1,sizeof(head)); tot=0;
31     memset(instack,false,sizeof(instack)); top=0;
32     memset(dfn,0,sizeof(dfn)); cnt=0;
33     scnt=0;
34 }
35 
36 void addedge(int u,int v){
37     e[tot].to=v; e[tot].nxt=head[u]; head[u]=tot++;
38 }
39 
40 void tarjan_dfs(int u){
41     dfn[u] = low[u] = ++cnt;
42     instack[u]=true;    //标记u已经在栈中
43     _stack[top++]=u;    //u入栈
44     for(int i=head[u];~i;i=e[i].nxt){
45         int to=e[i].to;
46         if( !dfn[to] ){ //未被访问,继续向下dfs
47             tarjan_dfs(to);
48            if( low[u]>low[to] ) low[u]=low[to]; //更新节点u所能到达的最小时间
49         }
50         else if( instack[to] && low[u]>dfn[to]){    //如果to已经在栈中
51             low[u]=dfn[to];
52         }
53     }
54     if( low[u]==dfn[u] ){   //如果节点u是强连通分量的根
55         scnt++; //连通分量个数加1
56         while(1){
57             int v=_stack[--top];    //退栈
58 //            printf("%d-",v);        //输出
59             instack[v]=false;       //标记不在栈中
60             belong[v]=scnt;         
61             if( v==u ) break;
62         }
63 //        printf("
");
64     }
65 }
66 
67 int main()
68 {
69     while( ~scanf("%d%d",&n,&m) && (n+m)){
70         init();
71         for(int i=0;i<m;i++){
72             int x,y; scanf("%d%d",&x,&y);
73             addedge(x,y);
74         }
75         for(int i=1;i<=n;i++){  //枚举每个节点,dfs搜联通分量
76             if(!dfn[i]){ 
77                 tarjan_dfs(i);
78             }
79         }
80         if( scnt==1 ) printf("Yes
");  //是一个强联通图
81         else printf("No
");        
82     }
83     return 0;
84 }