Tarjan算法求割点割边

Tarjan

美国著名科学家，全名 Robert Tarjan ，在图论和数据结构方面有着重要突出贡献。本文所介绍的算法是求解有向图强连通分量的算法，它能做到线性时间的复杂度。算法维护两个数组

• fdn[]：在DFS中，每个节点被访问的次序，即时间戳。
• low[]：在DFS中，每个节点不通过与父亲节点直接相连的边而访问的最早时间戳。

利用这两个数组可以求解许多问题，例如求割点、割边、强连通分量个数等。

当一个点是割点，满足下面的条件时成立：

• 如果节点u是总的DFS树的根，该节点u有多于1个的子树。
• 如果节点u不是总的DFS树的根，该节点u存在一颗子树，子树的根节点为v，且dfn[u]<=low[v]

而一条边(u,v)是割边，当且仅当这两点之间没有重边，而且dfn[u] < low[v]

算法实现

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 20001
// 割边集合
vector<vector<int>> edgeCut;
// vertexs[] 邻接表 verCut 割点集合
vector<int> vertexs[MAXN], verCut, item(2);
int dfn[MAXN], low[MAXN];
int n, m, countTime = 1;
void Tarjan(int nowVertex, int father = 0) {
    dfn[nowVertex] = low[nowVertex] = countTime++;
    int child, childTree = 0;
    bool flag = false;
    for (int i = 0; i < vertexs[nowVertex].size(); i++) {
        child = vertexs[nowVertex][i];
        if (child == father) continue;
        if (!dfn[child]) {
            childTree++;
            Tarjan(child, nowVertex);
            if (dfn[nowVertex] <= low[child]) flag = true;
            low[nowVertex] = min(low[nowVertex], low[child]);
        } else
            low[nowVertex] = min(low[nowVertex], dfn[child]);
    }
    if ((!father && childTree > 1) || (father && flag))
        verCut.push_back(nowVertex);
    if (father && low[nowVertex] > dfn[father]) {
        item[0] = father;
        item[1] = nowVertex;
        edgeCut.push_back(item);
    }
}
int main() {
    memset(dfn, 0, sizeof(dfn));
    int u, v;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        vertexs[u].push_back(v);
        vertexs[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) Tarjan(i);
    /* for (int i = 1; i <= n; i++)
        printf("%d : %d ---- %d \n", i, dfn[i], low[i]); */
    printf("verCut's is : %d\n", verCut.size());
    if (verCut.size() > 0) {
        sort(verCut.begin(), verCut.end());
        for (int i = 0; i < verCut.size(); i++) printf("%d ", verCut[i]);
    }
    printf("\ndgeCut's is : %d\n", edgeCut.size());
    if (edgeCut.size() > 0) {
        for (int i = 0; i < edgeCut.size(); i++)
            printf("%d---%d\n", edgeCut[i][0], edgeCut[i][1]);
    }
    return 0;
}
/*

6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6

8 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6



8 8
1 2
1 3
2 3
2 4
5 6
5 7
6 7
7 8

6 6
1 2
1 3
2 3
2 4
2 5
5 6
*/