有向图连通分量SCC

在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，称该图为非连通图，则其中的极大连通子图称为连通分量，这里所谓的极大是指子图中包含的顶点个数极大。

直观地说，极大就是不能再大，或者说再大也不能超过自己。因此，极大连通子图就是：
　　设
　　1) S为G的子图，S连通，
　　2) 如果有S'也是G的连通子图，且S是S'的子图，可推出S = S'，
　　则称S是G的极大连通子图。
　　极小连通子图正好相反，极小就是不能再小，再多小一点就会不连通或点不足。因此，极小连通子图就是：
　　设
　　1) S为G的子图，S连通，
　　2) 如果有S'也是G的连通子图，S'包含G的所有顶点，且S'是S的子图，可推出S' = S，
　　则称S是G的级小连通子图。
　　注：这个定义和pinejeely给出的等价。这里给出的定义比较容易验证。

在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大强连通子图称为强连通分量。

Kosaraju算法：先dfs，得到最后完成时间f，再求反图，按f递减的方向对反图再dfs一次。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <algorithm>
  4 #include <iomanip>
  5 #include <set>
  6 #include <map>
  7 #include <vector>
  8 #include <queue>
  9 using namespace std;
 10 #define N 1000
 11 int head[N], headt[N], cnt;
 12 struct node 
 13 {
 14     int next, to;
 15 }edge[N * 2], edget[N * 2];
 16 
 17 void addedge(int from, int to)//G_T
 18 {
 19     cnt++;
 20     edge[cnt].next = head[from];
 21     edge[cnt].to = to;
 22     head[from] = cnt;
 23     //得到反图
 24     edget[cnt].next = headt[to];
 25     edget[cnt].to = from;
 26     headt[to] = cnt;
 27 }
 28 int f[N];//finishtime
 29 int d[N];//discovertime
 30 int color[N];//init 0 denote white; 1 denote gray discover; 2 denote black finish 
 31 int time; 
 32 int belong[N];//which scc
 33 int cur;//current scc
 34 void dfs_visit(int x)
 35 {
 36     color[x] = 1;
 37     d[x] = ++time;
 38     int i, j;
 39     for (i = head[x]; i; i = edge[i].next)
 40     {
 41         j = edge[i].to;
 42         if (!color[j])
 43         {
 44             dfs_visit(j);
 45         }
 46     }
 47     //color[x] = 2;
 48     f[x] = ++time;
 49 }
 50 
 51 void dfs_visit_t(int x)
 52 {
 53     color[x] = 1;
 54     //d[x] = ++time;
 55     int i, j;
 56     for (i = headt[x]; i; i = edget[i].next)
 57     {
 58         j = edget[i].to;
 59         if (!color[j])
 60         {
 61             dfs_visit_t(j);
 62         }
 63     }
 64     //color[x] = 2;
 65     //f[x] = ++time;
 66     belong[x] = cur;
 67 }
 68 
 69 bool cmp(const int &a, const int &b)
 70 {
 71     return a > b;
 72 }
 73 
 74 map<int, int, greater<int> > mp;//使用map对f[i]进行从大到小排序
 75 map<int, int>::iterator it;
 76 
 77 void init()
 78 {
 79     cnt = cur = 1;
 80     time = -1;
 81     memset(head, 0, sizeof(head));
 82     memset(f, 0, sizeof(f));
 83     memset(d, 0, sizeof(d));
 84     memset(color, 0, sizeof(color));
 85     memset(belong, 0, sizeof(belong));
 86     mp.clear();
 87 }
 88 
 89 int main()
 90 {
 91     int n, m, u, v, i;
 92     while (~scanf("%d%d", &n, &m))
 93     {
 94         init();
 95         for (i = 0; i < m; i++)
 96         {
 97             scanf("%d%d", &u, &v);
 98              addedge(u, v);
 99         } 
100         for (i = 1; i <= n; i++)//得到f
101             if (!color[i])
102                 dfs_visit(i);
103         //sort(f, f + n, cmp);
104         for (i = 1; i <=n; i++)//对f排序
105             mp[f[i]] = i;    
106         memset(color, 0, sizeof(color));
107         for (it = mp.begin(); it != mp.end(); ++it)//对反图进行dfs
108         {
109             if (!color[it->second])
110             {
111                 dfs_visit_t(it->second);
112                 cur++;
113             }        
114         }    
115         for (i = 1; i <=n; i++)
116             printf("%d ", belong[i]);
117     }
118     return 0;
119 }

Tarjan算法只需一次dfs，而且不用求反图，dfs找最早祖先点(最先被发现)也就是寻找B边。

使用LOW函数测试此条件

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <iomanip>
 5 #include <set>
 6 #include <map>
 7 #include <vector>
 8 #include <queue>
 9 #include <stack>
10 #define INF 0x7fffffff
11 using namespace std;
12 #define N 1000
13 
14 stack<int> s;
15 int head[N], cnt;
16 struct node 
17 {
18     int next, to;
19 }edge[N * 2];
20 
21 void addedge(int from, int to)
22 {
23     cnt++;
24     edge[cnt].next = head[from];
25     edge[cnt].to = to;
26     head[from] = cnt;
27 }
28 //int f[N];//finishtime
29 int pre[N];//discovertime 
30 //int color[N];//init 0 denote white; 1 denote gray discover; 2 denote black finish 
31 int time; 
32 int id[N];//which scc
33 int low[N];//
34 int cur;//current scc
35 void dfs_visit(int x)
36 {
37     low[x] = pre[x] = ++time;
38     s.push(x);
39     int i, j;
40     for (i = head[x]; i; i = edge[i].next)
41     {
42         j = edge[i].to;
43         if (!pre[j])
44         {
45             dfs_visit(j);
46         }
47         if (low[j] < low[x])//找最小的low[x]，即是否存在后向边(B边)
48             low[x] = low[j];
49     }
50     if (low[x] == pre[x])//找到了一个scc
51     {
52         do
53         {
54             i = s.top();
55             s.pop();
56             low[i] = INF;
57             id[i] = cur;
58         }while (i != x);
59         cur++;
60     }
61 }
62 
63 void init()
64 {
65     cnt = cur = 1;
66     time = 0;
67     memset(head, 0, sizeof(head));
68     memset(pre, 0, sizeof(pre));
69     memset(low, 0, sizeof(low));
70     memset(id, 0, sizeof(id));
71     while (!s.empty())
72         s.pop();
73 }
74 
75 int main()
76 {
77     int n, m, u, v, i;
78     while (~scanf("%d%d", &n, &m))
79     {
80         init();
81         for (i = 0; i < m; i++)
82         {
83             scanf("%d%d", &u, &v);
84              addedge(u, v);
85         }     
86         for (i = 1; i <= n; i++)
87             if (!pre[i])
88                 dfs_visit(i);
89         for (i = 1; i <=n; i++)
90             printf("%d ", id[i]);
91     }
92     return 0;
93 }

Gabow算法：思路与tarjan思路一样,但是用一个stack替代了low数组，使得交换次数减小

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <iomanip>
 5 #include <set>
 6 #include <map>
 7 #include <vector>
 8 #include <queue>
 9 #include <stack>
10 #define INF 0x7fffffff
11 using namespace std;
12 #define N 1000
13 
14 stack<int> s;
15 stack<int> p;
16 int head[N], cnt;
17 struct node 
18 {
19     int next, to;
20 }edge[N * 2];
21 
22 void addedge(int from, int to)
23 {
24     cnt++;
25     edge[cnt].next = head[from];
26     edge[cnt].to = to;
27     head[from] = cnt;
28 }
29 //int f[N];//finishtime
30 int pre[N];//discovertime 
31 //int color[N];//init 0 denote white; 1 denote gray discover; 2 denote black finish 
32 int time; 
33 int id[N];//which scc
34 int low[N];//
35 int cur;//current scc
36 void dfs_visit(int x)
37 {
38     low[x] = pre[x] = ++time;
39     s.push(x);
40     p.push(x);
41     int i, j;
42     for (i = head[x]; i; i = edge[i].next)
43     {
44         j = edge[i].to;
45         if (!pre[j])
46             dfs_visit(j);
47         if (!id[j])//该点未在已求的scc中
48             while (pre[j] < pre[p.top()])存在后向边，出栈
49                 p.pop();    
50     }
51     if (p.top() == x)//找到一个scc
52     {
53         p.pop();
54         do
55         {
56             i = s.top();
57             id[i] = cur;
58             s.pop();
59         }while (i != x);
60         cur++;
61     }
62 }
63 
64 void init()
65 {
66     cnt = cur = 1;
67     time = 0;
68     memset(head, 0, sizeof(head));
69     memset(pre, 0, sizeof(pre));
70     memset(low, 0, sizeof(low));
71     memset(id, 0, sizeof(id));
72     while (!s.empty())
73         s.pop();
74     while (!p.empty())
75         p.pop();
76 }
77 
78 int main()
79 {
80     int n, m, u, v, i;
81     while (~scanf("%d%d", &n, &m))
82     {
83         init();
84         for (i = 0; i < m; i++)
85         {
86             scanf("%d%d", &u, &v);
87              addedge(u, v);
88         }     
89         for (i = 1; i <= n; i++)
90             if (!pre[i])
91                 dfs_visit(i);
92         for (i = 1; i <=n; i++)
93             printf("%d ", id[i]);
94     }
95     return 0;
96 }