.

Tarjan算法：

dfn[ ]: 该点dfs的时间戳

low[ ]: 该点可以通过非当前dfs路径到达的最小的时间戳

tarjan核心思想：一个父节点u，一个子节点v， 若low[v] >= dfn[u]，则说明当前这个父节点对子节点具有绝对的控制，换言之，这个父节点与子节点之间的边要是断了，那么子节点没有其他路径可以到达一个时间戳更小的点去，那么这个连通分量就断开了，所以这条边就是割边，这个父节点（多半）是割点（如果是根节点的话还要判断一下）。

边双连通分量（EDCC）：一个无向图中，没有割边。一般图中，去掉割边，剩下的就是各个边双。

点双连通分量（VDCC）：一个无向图中，没有割点。求点双不是直接去掉割点。

强连通分量（SCC）：一个有向图中，任意点之间相互连通的极大连通分量

除了求边双可以用去掉割边再求联通分量的，其他过程中涉及到用stack保存dfs的顺序，从而得到各个连通块的方法，求边双也可以用stack。

1、求割边及边双联通分量（EDCC）：

​ 注意：两个点间可能有多条边，所以要记录各个边。

​ 小技巧：从2开始记录边，2+1则是反边， 这样的话对每个边i，它的反边就是(i ^ 1)

题目：P8436

解法1：

​ 先求出割边，再去掉割边，再求出连通块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
#define PII pair<int, int>

void solve(){
    int n,m;
    cin>>n>>m;

    vector<vector<PII>> adj(n + 1);
    vector<bool> st(2 * m + 10, false);
    for(int i = 1; i <= m; ++i){
        int u,v;
        cin>>u>>v;
        adj[u].push_back({v,i << 1});
        adj[v].push_back({u,i << 1 ^ 1});
    }

    vector<int> dfn(n + 1, 0);
    vector<int> low(n + 1, 0);
    int tim = 0;
    function<void(int, int)> tarjan = [&](int u, int fa){
        dfn[u] = low[u] = ++tim;
        for(auto [v, vis] : adj[u]){
            if(vis == (fa ^ 1)){//不能从来的陆回去
                continue;
            }
            if(!dfn[v]){
                tarjan(v,vis);
                low[u] = min(low[u], low[v]);
                if(low[v] >= dfn[u]){ //u对v有支配关系
                    st[(vis)] = true; // 记录割边
                    st[(vis ^ 1)] = true;
                }
            }
            else{
                low[u] = min(low[u], dfn[v]);
            }
        }
        return ;
    };

    for(int i = 1; i <= n; ++i){
        if(!dfn[i]){
            tarjan(i,-1);
        }
    }

    vector<vector<int>> EDCC(n + 1);
    for(int u = 1; u <= n; ++u){
        for(auto [v, w] : adj[u]){
            if(st[w] || st[w ^ 1]){
                continue;
            }
            else{
                EDCC[u].push_back(v);
            }
        }
    }

    vector<bool> vis(n + 1, false);
    int cnt = 0;
    vector<vector<int>> ans(n + 1);
    function<void(int)> dfs = [&](int u){
        vis[u] = true;
        ans[cnt].push_back(u);
        for(auto v : EDCC[u]){
            if(vis[v]){
                continue;
            }
            dfs(v);
        }
        return ;
    };   

    for(int i = 1; i <= n; ++i){
        if(!vis[i]){
            cnt ++;
            dfs(i);
        }
    }

    cout<<cnt<<"\n";

    for(int i = 1; i <= cnt; ++i){
        cout<<ans[i].size()<<" ";
        for(auto v : ans[i]){
            cout<<v<<" ";
        }
        cout<<"\n";
    }


    return ;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

解法2：

​ 直接stack模拟，速度快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
#define PII pair<int, int>

void solve(){
    int n,m;
    cin>>n>>m;

    vector<vector<PII>> adj(n + 1);
    vector<bool> st(2 * m + 10, false);
    for(int i = 1; i <= m; ++i){
        int u,v;
        cin>>u>>v;
        adj[u].push_back({v,i << 1});
        adj[v].push_back({u,i << 1 ^ 1});
    }

    vector<int> dfn(n + 1, 0);
    vector<int> low(n + 1, 0);
    int tim = 0;
    stack<int> stk;
    vector<vector<int>> ans(n + 1);
    int cnt = 0;
    function<void(int, int)> tarjan = [&](int u, int fa){
        dfn[u] = low[u] = ++tim;
        stk.push(u);
        for(auto [v, vis] : adj[u]){
            if(vis == (fa ^ 1)){//不能从来的陆回去
                continue;
            }
            if(!dfn[v]){
                tarjan(v,vis);
                low[u] = min(low[u], low[v]);
                if(low[v] >= dfn[u]){ //u对v有支配关系
                    st[(vis)] = true; // 记录割边
                    st[(vis ^ 1)] = true;
                }
            }
            else{
                low[u] = min(low[u], dfn[v]);
            }
        }
        if(low[u] == dfn[u]){ //此时求得了极大的联通分量。
            int v;
            cnt ++;
            do{
                v = stk.top();
                stk.pop();
                ans[cnt].push_back(v);
            }while(v != u);
        }
        return ;
    };

    for(int i = 1; i <= n; ++i){
        if(!dfn[i]){
            tarjan(i,-1);
        }
    }

    cout<<cnt<<"\n";
    for(int i = 1; i <= cnt; ++i){
        cout<<ans[i].size()<<" ";
        for(auto v : ans[i]){
            cout<<v<<" ";
        }
        cout<<"\n";
    }

    return ;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

2、求割点及点双连通分量（VDCC）：

1、求割点

​ 如果一个点不是根节点，且有可以支配的子节点，那么他就是一个割点；如果这个点是根节点，那么需要两个可支配的子节点。

题目：P3388

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
#define PII pair<int, int>

void solve(){
    int n,m;
    cin>>n>>m;

    vector<vector<int>> adj(n + 1);
    for(int i = 1; i <= m; ++i){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> dfn(n + 1, 0);
    vector<int> low(n + 1, 0);
    vector<bool> cut(n + 1, false);
    int tim = 0;

    function<void(int, int)> tarjan = [&](int u,int fa){
        dfn[u] = low[u] = ++tim;
        int cnt = 0;
        for(auto v : adj[u]){
            if(!dfn[v]){
                tarjan(v,u);
                low[u] = min(low[u], low[v]);
                if(low[v] >= dfn[u]){
                    cnt ++;
                    if(fa != -1 || cnt >= 2){
                        cut[u] = true;
                    }
                }
                
            } 
            else{
                low[u] = min(low[u], dfn[v]);
            }
        }
        return ;
    };

    for(int i = 1; i <= n; ++i){
        if(!dfn[i]){
            tarjan(i,-1);
        }
    }

    vector<int> ans;
    for(int i = 1; i <= n; ++i){
        if(cut[i]){
            ans.push_back(i);
        }
    }
    cout<<ans.size()<<"\n";

    for(auto it : ans){
        cout<<it<<" ";
    }
    cout<<"\n";

    return ;

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

2、求点双连通分量：

​ 每找到一个割点，就在就把栈中到这个割点的孩子的所有点添加进点双，并加入割点。（注意此时不能把割点从栈中删去，因为割点可能在多个点双中。）

​ 注意：求解的时候记得把自环去掉，否则对于一些孤立的点来说，他们就无法被添加进点双中。

题目：P8435

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
#define PII pair<int, int>

void solve(){
    int n,m;
    cin>>n>>m;

    vector<vector<int>> adj(n + 1);
    for(int i = 1; i <= m; ++i){
        int u,v;
        cin>>u>>v;
        if(u == v){//去掉自环
            continue;
        }
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> dfn(n + 1, 0);
    vector<int> low(n + 1, 0);
    vector<bool> cut(n + 1, false);
    stack<int> stk;
    int tim = 0;
    int sum = 0;
    vector<vector<int>> ans(n + 1);
    function<void(int, int)> tarjan = [&](int u,int fa){
        dfn[u] = low[u] = ++tim;
        stk.push(u);
        int cnt = 0;
        if(adj[u].size() == 0){ //孤立的点特判一下
            sum ++;
            ans[sum].push_back(u);
        }
        for(auto v : adj[u]){
            if(!dfn[v]){
                tarjan(v,u);
                low[u] = min(low[u], low[v]);
                if(low[v] >= dfn[u]){
                    cnt ++;
                    if(u != -1 || cnt >= 2){
                        int to = 0;
                        sum ++;
                        do{
                            to = stk.top();
                            stk.pop();
                            ans[sum].push_back(to);
                        }while(to != v);
                        ans[sum].push_back(u);
                        cut[u] = true;
                    }
                }
            } 
            else{
                low[u] = min(low[u], dfn[v]);
            }
        }
        return ;
    };

    for(int i = 1; i <= n; ++i){
        if(!dfn[i]){
            tarjan(i,-1);
        }
    }

    cout<<sum<<"\n";
    for(int i = 1; i <= sum; ++i){
        cout<<ans[i].size()<<" ";
        for(auto it : ans[i]){
            cout<<it<<" ";
        }
        cout<<"\n";
    }

    return ;

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

3、求强连通分量（SCC）：

​ 1、每访问到一个点x，将他压入栈中，遍历所有邻接点y。

​ 2、如果邻接点y已经在栈中了，说明邻接点的dfn[]更小，更新low[x] = min(low[x], dfn[y]);

​ 3、如果没在栈中，就递归访问y，返回时更新low[x] = min(low[x], low[y]);

​ 4、当前节点遍历完，如果dfn[x] == low[x]，则说明当前点是一个强连通分量的起点，此时一直弹栈，直到弹出当前点x，这些点构成一个强连通分量。

​ 每一个dfn等于low的点，后面的点都是有其他方式可以访问到更早点的，但是当前点没法访问到更早的点，所以它可以作为一个强连通分量的起点。

​ 5、入栈或出栈用一个st数组记录。

题目 ：P3387

代码中的SCC即是缩点之后的新图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
#define PII pair<int, int>


void solve(){
    int n,m;
    cin>>n>>m;

    vector<vector<int>> adj(n + 1);
    vector<int> a(n + 1);
    for(int i = 1; i <= n; ++i){
        cin>>a[i];
    }
    for(int i = 1; i <= m; ++i){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
    }

    vector<int> dfn(n + 1, 0);
    vector<int> low(n + 1, 0);
    vector<bool> st(n + 1, false);
    vector<int> bel(n + 1, -1);
    stack<int> stk;
    int cnt = 0;
    int tim = 0;
    function<void(int)> tarjan = [&](int u){
        dfn[u] = low[u] = ++tim;
        st[u] = true;
        stk.push(u);
        for(auto v : adj[u]){
            if(!dfn[v]){
                tarjan(v);
                low[u] = min(low[u], low[v]);
            } 
            else if(st[v]){
                low[u] = min(low[u], dfn[v]);
            }
        }

        if(low[u] == dfn[u]){
            int v;
            cnt ++;
            do{
                v = stk.top();
                stk.pop();
                bel[v] = cnt;
                st[v] = false;
            }while(u != v);
        }

        return ;
    };

    for(int i = 1; i <= n; ++i){
        if(!dfn[i]){
            tarjan(i);
        }
    }

    vector<int> b(n + 1);
    for(int i = 1; i <= n; ++i){
        int x = bel[i];
        b[x] += a[i];
    }

    vector<vector<int>> SCC(n + 1);
    for(int u = 1; u <= n; ++u){
        for(auto v : adj[u]){
            if(bel[u] == bel[v]){
                continue;
            }
            else{
                int x = bel[u];
                int y = bel[v];
                SCC[x].push_back(y);
            }
        }
    }

    for(int i = 1; i <= cnt; ++i){
        SCC[0].push_back(i);
    }

    vector<bool> vis(n + 1, false);
    vector<int> dis(n + 1, 0);
    vector<int> sum(n + 1, 0);
    queue<int> qu;
    vis[0] = true;
    dis[0] = 0;
    qu.push(0);
    bool f = true;
    while(!qu.empty() && f){
        auto x = qu.front();
        qu.pop();
        vis[x] = false;
        for(auto y : SCC[x]){
            if(dis[y] > dis[x] + (-b[y])){
                dis[y] = dis[x] - b[y];
                if(!vis[y]){
                    if(++sum[y] >= n){
                        f = false;
                    }
                    vis[y] = true;
                    qu.push(y);
                }
            }
        }
    }

    int ans = 0;
    for(int i = 1; i <= cnt; ++i){
        ans = min(ans, dis[i]);
    }

    ans = -ans;
    cout<<ans<<"\n";

    return ;

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}