Tarjan 求割点

割点的定义

关节点的定义：在一个连通图中，如果去掉某个点会导致整个图变成非连通图，那么这个点就是割点。

算法

前置知识：深度优先搜索。

对于一个图，我们可以按 DFS 序生成一个数组，存储每一个元素是第几个访问的：dfn[]。

我们定义 L[i] 为不经过其父亲能到达的最小的时间戳。

• 对于每一个 l[i]，最初始的值是 dfn[i]。
• 如果 $v$ 是 $i$ 的子树，那么 l[i] = min(l[i], l[v])。
• 如果 $v$ 和 $i$ 的子树中的一个点有回边，那么 l[i] = min(l[i], l[v])。

代码

#include <bits/stdc++.h>
using namespace std;
int n, a[105][105];
int dfn[1005], l[1005], cnt, vis[1005];
//vector <int> ans;
int cntt;
int ans[100005];

void dfs(int u) {
    dfn[u] = ++cnt;
    vis[u] = 1;
    l[u] = dfn[u];

    for (int v = 1; v <= n; v ++) {
        if (a[u][v] == 1) {
            //是子节点
            a[u][v] = a[v][u] = 0;

            if (vis[v] == 0) {
                if (dfn[u] == 1) {
                    cntt ++;

                    if (cntt == 2) {
                        ans[u] = 1;
                    }
                }

                dfs(v);
                l[u] = min(l[u], l[v]);

                if (dfn[u] <= l[v]) {
                    if (dfn[u] != 1)
                        ans[u] = 1;
                }
            } else {
                l[u] = min(l[u], dfn[v]);
            }
        }
    }
}

int main() {
    cin >> n;

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            cin >> a[i][j];
        }
    }

    dfs(1);
    int cnttt = 0;

    for (int i = 1; i <= 100000; i ++) {
        if (ans[i])
            cout << i << " ", cnttt = 1;
    } 

    if (cnttt == 0)
        cout << "safe";
}

Tarjan 求桥

桥的定义

桥和关节点类似，定义为：在一个连通图中，如果去掉某个边会导致整个图变成非连通图，那么这个点就是桥。

算法

算法和割点类似，只要把代码中的 dfn[u] <= l[v] 改成 dfn[u] < l[v] 就行了，而且不需要考虑根节点的问题。

例题

P7687 CEOI2005 Critical Network Lines – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, K, L;
int dfn[100005], l[100005], cnt, vis[100005];
// vector <int> ans;
int cntt;
vector <pair <int, int> > ans;
int tpe[100005];
int cnta[100005], cntb[100005];
//1 -> A
//2 -> B
vector <int> e[100005];

void dfs(int u, int fa) {
    dfn[u] = ++cnt;
    vis[u] = 1;
    l[u] = dfn[u];
    for (int i = 0; i < e[u].size(); i ++) {
        int v = e[u][i];
        if (v == fa) continue;

            if (vis[v] == 0) {
                dfs(v, u);
                l[u] = min(l[u], l[v]);
                if (l[v] > dfn[u]) if (cnta[v] == 0 || cntb[v] == 0 || cnta[v] == K || cntb[v] == L) ans.push_back(make_pair(u, v));

                    cnta[u] += cnta[v];
    cntb[u] += cntb[v];
            } else {
                l[u] = min(l[u], dfn[v]);
            }
    }

}

int main() {
    cin >> n >> m >> K >> L; 

    for (int i = 1; i <= K; i ++) {
        int x; cin >> x;
        cnta[x] ++;
    }
    for (int i = 1; i <= L; i ++) {
        int x; cin >> x;
        cntb[x] ++;
    }
    while (m --) {
        int x, y; cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    // for (int i = 1; i <= n; i ++) {
    //  for (int j = 1; j <= n; j ++) {
    //      cin >> a[i][j];
    //  }
    // }

    dfs(1, 0);
    int cnttt = 0;

    // for (int i = 1; i <= 100000; i ++) {
    //  if (ans[i])
    //      cout << i << " ", cnttt = 1;
    // } 
    cout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); i ++) {
        cout << ans[i].first << " " << ans[i].second << "\n";
    }
}