学渣乱搞系列之Tarjan模板合集

学渣乱搞系列之Tarjan模板合集

　　　　　　　　　　　　by　狂徒归来

一、求强连通子图

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define pii pair<int,int>
15 #define INF 0x3f3f3f3f
16 using namespace std;
17 const int maxn = 20100;
18 int dfn[maxn],low[maxn],belong[maxn];
19 bool instack[maxn];
20 vector<int>g[maxn];
21 stack<int>stk;
22 int n,m,cnt,scc;
23 void tarjan(int u) {
24     dfn[u] = low[u] = ++cnt;
25     stk.push(u);
26     instack[u] = true;
27     for(int i = 0; i < g[u].size(); i++) {
28         if(!dfn[g[u][i]]) {
29             tarjan(g[u][i]);
30             low[u] = min(low[u],low[g[u][i]]);
31         } else if(instack[g[u][i]]) low[u] = min(low[u],dfn[g[u][i]]);
32     }
33     if(dfn[u] == low[u]) {
34         scc++;
35         int v;
36         do {
37             v = stk.top();
38             instack[v] = false;
39             belong[v] = scc;
40             stk.pop();
41         } while(v != u);//每一个强连通块内de点，以及其属于的scc
42     }
43 }
44 int main() {
45     int i,j,u,v,a,b;
46     while(~scanf("%d %d",&n,&m)) {
47         for(i = 0; i <= n; i++) {
48             dfn[i] = belong[i] = 0;
49             instack[i] = false;
50             g[i].clear();
51         }
52         cnt = scc = 0;
53         while(!stk.empty()) stk.pop();
54         for(i = 1; i <= m; i++) {
55             scanf("%d %d",&u,&v);
56             g[u].push_back(v);
57         }
58         for(i = 1; i <= n; i++)
59             if(!dfn[i]) tarjan(i);
60     }
61     return 0;
62 }

View Code

二、求割点

 1 const int maxn = 1010;
 2 vector<int>g[maxn];
 3 bool iscut[maxn];
 4 int dfn[maxn],low[maxn],cnt,vis[maxn];
 5 void tarjan(int u,int fa) {
 6     dfn[u] = low[u] = ++cnt;
 7     vis[u] = 1;
 8     int son = 0;
 9     for(int i = 0; i < g[u].size(); i++) {
10         if(!vis[g[u][i]]) {
11             tarjan(g[u][i],u);
12             son++;
13             low[u] = min(low[u],low[g[u][i]]);
14             if(fa == -1 && son > 1 || fa != -1 && low[g[u][i]] >= dfn[u])
15                 iscut[u] = true;
16         } else if(vis[g[u][i]] == 1) low[u] = min(low[u],dfn[g[u][i]]);
17     }
18     vis[u] = 2;
19 }

三、求割边/桥

 1 int ret;
 2 void tarjan(int u,int fa) {
 3     dfn[u] = low[u] = ++clk;
 4     bool flag = false;
 5     for(int i = head[u]; ~i; i = e[i].next) {
 6         if(!flag && e[i].to == fa) {
 7             flag = true;
 8             continue;
 9         }
10         if(!dfn[e[i].to]) {
11             tarjan(e[i].to,u);
12             low[u] = min(low[u],low[e[i].to]);
13             if(low[e[i].to] > dfn[u]) {
14                 e[i].cut = e[i^1].cut = true;
15                 ++ret;
16             }
17         } else low[u] = min(low[u],dfn[e[i].to]);
18     }
19 }

四、求LCA