无向图的割顶和桥、无向图的双连通分量、有向图的强连通分量

总结自《算法竞赛入门经典——训练指南》（刘汝佳），具体分析请详见书中解析。

时间戳：说白了就是记录下访问每个结点的次序。假设我们用 pre 保存，那么如果 pre[u] > pre[v]，那么就可以知道先访问的 v ，后访问的 u 。

现在给定一条边， (u, v)，且 u 的祖先为 fa, 如果有 pre[v] < pre[u] && v != fa, 那么 (u, v) 为一条反向边。

无向图的割顶和桥：

求割顶：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <queue>
#include <map>

using namespace std;

const int maxn = 1000;

vector<int> G[maxn];
int pre[maxn], dfs_clock, low[maxn], n;
bool iscut[maxn];

void init(){
    for(int i=0; i<n; i++) G[i].clear();
    memset(iscut, false, sizeof(iscut));
    memset(pre, 0, sizeof(pre));
    dfs_clock = 0;
}

int dfs(int u, int fa){ //u在DFS树中的父结点是fa
    int lowu = pre[u] = ++dfs_clock;
    int child = 0; //子结点数目
    for(int i=0; i<G[u].size(); i++){
        int v = G[u][i];
        if(!pre[v]){    //没有访问过v, 没有必要用vis标记了
            child++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv); //用后代的 low 函数更新 u 的 low 函数
            if(lowv >= pre[u]){
                iscut[u] = true;
            }
        }
        else if(pre[v] < pre[u] && v != fa){ //(u,v)为反向边
            lowu = min(lowu, pre[v]);   //用反向边更新 u 的 low 函数
        }
        if(fa < 0 && child == 1) iscut[u] = false;
    }
    low[u] = lowu;
    return lowu;
}

int main(){
    int m, u, v;
    scanf("%d%d", &n, &m);

    init();

    for(int i=0; i<m; i++){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    for(int i=0; i<n; i++)if(!pre[i]){
        dfs(i, -1);
    }

    for(int i=0; i<n; i++){ //将割点输出
        if(iscut[i]) printf("%d ", i);
    }
    putchar('\n');

    return 0;
}

View Code

桥：

如果v的后代只能连回 v 自己（即 low(v) > pre[u)), 只需删除(u, v)一条边就可以让图G非连通了，满足这个条件的边称为桥。换句话说，我们不仅知道结点u是割顶，还知道了（u，v）是桥。

样例：

12 12
0 1
0 4
4 8
8 9
4 9
2 3
2 7
2 6
6 7
3 7
10 7
7 11

无向图的双连通分量：

割顶的bccno无意义：割点的bccno会被多次赋值，所以它的值无意义。

调用结束后， S保证为空：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <queue>
#include <map>

using namespace std;

const int maxn = 1000+10;

int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt;
vector<int> G[maxn], bcc[maxn];

struct Edge{
    int u, v;
};

stack<Edge> S;

int dfs(int u, int fa){
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int i=0; i<G[u].size(); i++){
        int v = G[u][i];
        Edge e = (Edge){u, v};
        if(!pre[v]){
            S.push(e);
            child++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if(lowv >= pre[u]){
                iscut[u] = true;
                bcc_cnt++; bcc[bcc_cnt].clear();
                for(;;){
                    Edge x = S.top(); S.pop();
                    if(bccno[x.u] != bcc_cnt) {
                        bcc[bcc_cnt].push_back(x.u);
                        bccno[x.u] = bcc_cnt;
                    }
                    if(bccno[x.v] != bcc_cnt) {
                        bcc[bcc_cnt].push_back(x.v);
                        bccno[x.v] = bcc_cnt;
                    }
                    if(x.u == u && x.v == v) break;
                }
            }
        }
        else if(pre[v] < pre[u] && v != fa){
            S.push(e);
            lowu = min(lowu, pre[v]);
        }
    }
    if(fa < 0 && child == 1) iscut[u] = 0;
    return lowu;
}

void find_bcc(int n){
    memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    dfs_clock = bcc_cnt = 0;
    for(int i=0; i<n; i++){
        if(!pre[i]) dfs(i, -1);
    }
}

int main(){
    int m, u, v, n;
    scanf("%d%d", &n, &m);

    for(int i=0; i<m; i++){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    find_bcc(n);

    printf("%d\n", bcc_cnt);    //双连通分量的个数
    for(int i=1; i<=bcc_cnt; i++){  //输出每个双连通分量
        for(int j=0; j<bcc[i].size(); j++){
            printf("%d ", bcc[i][j]);
        }
        putchar('\n');
    }

    return 0;
}

View Code

样例：

5 6
0 1
0 2
1 2
2 3
2 4
3 4

有向图的强连通分量：

运行完DFS栈为什么始终为空：

换种说法， w->u->v->e, e->u, 将u, v, e 找出后，什么时候弹出的 w ？因为对于 w, 它的 lowlink 和 pre 相等，因此 w 作为一个 SCC，会被弹出。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>

using namespace std;

const int maxn = 2000;
int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;
vector<int> G[maxn];
stack<int> S;

void dfs(int u){
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);
    for(int i=0; i<G[u].size(); i++){
        int v = G[u][i];
        if(!pre[v]){
            dfs(v);
            lowlink[u] = min(lowlink[u], lowlink[v]);
        }
        else if(!sccno[v]){
            lowlink[u] = min(lowlink[u], pre[v]);
        }
    }
    if(lowlink[u] == pre[u]){
        scc_cnt++;
        for(;;){
            int x = S.top(); S.pop();
            sccno[x] = scc_cnt;
            if(x == u) break;
        }
    }
}
void find_scc(int n){
    //栈始终为空，不用初始化
    dfs_clock = scc_cnt = 0;
    memset(sccno, 0, sizeof(sccno));
    memset(pre, 0, sizeof(pre));
    for(int i=0; i<n; i++){
        if(!pre[i]) dfs(i);
    }
}
int main(){
    int n, m, u, v;
    scanf("%d%d", &n, &m);
    for(int i=0; i<n; i++) G[i].clear();
    for(int i=0; i<m; i++){
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    find_scc(n);
    for(int i=1; i<=scc_cnt; i++){
        for(int j=0; j<n; j++) if(sccno[j] == i) printf("%d ", j);
        putchar('\n');
    }
    return 0;
}

View Code

样例：

12 17

0 1

1 2

1 3

1 4

2 5

4 1

4 5

4 6

5 2

5 7

6 7

6 9

7 10

8 6

9 8

10 11

11 9