tarjan 割点 割边

· · 个人记录

割点的定义

对于一个无向图，删除一个点，图的极大联通分量增加，这个点就是一个割点。

实现步骤

很容易想到的是，暴力枚举每一条边和点，但时间复杂度太高，考虑优化。

我们可以使用 Tarjan，记录 dfn_i 为第 i 个点的时间戳，low_i 表示通过回边（非父子边）能回到的最小时间戳的节点。

对于根节点，若其有两棵及以上的子树，则根节点为割点。

因为如果去掉根节点，两棵子树将无法互相连通。

对于不是根节点的 u，若有一儿子节点 v，无法通过回边回到除 u 外的其他父亲节点，则 u 为割点，即 low_v \geq dfn_u。

P3388 【模板】割点（割顶）

#include <bits/stdc++.h>

using namespace std;

const int N = 2e4 + 10;

int n, m, dfn[N], low[N], tim, root, cnt;
bool vis[N];
vector<int> nbr[N];

void tarjan(int u) {
    int sum = 0;
    dfn[u] = low[u] = ++tim;
    for (int v : nbr[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                sum++;
                if (u != root || sum >= 2)
                    (vis[u] == 0) && (cnt++, vis[u] = 1);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        nbr[u].push_back(v);
        nbr[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i])
            root = i, tarjan(i);
    }
    cout << cnt << '\n';
    for (int i = 1; i <= n; i++) {
        if (vis[i])
            cout << i << ' ';
    }
    return 0;
}

HDU-4738 Caocao's Bridges

问题转化后即求边权最小值。

注意数组范围，本题很迷。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e3 + 10;

int n, m, head[N], dfn[N], low[N], tim, tot, ans;
bool bridge[2 * N * N];

struct Edge {
    int v, nxt, w;
} edges[N * N * 2];

void add_edge(int u, int v, int w) {
    edges[++tot].v = v;
    edges[tot].nxt = head[u];
    edges[tot].w = w;
    head[u] = tot;
}

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++tim;
    for (int i = head[u]; i; i = edges[i].nxt) {
        int v = edges[i].v;
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                bridge[i] = bridge[i ^ 1] = 1;
            }
        } else if (i != (fa ^ 1)) {
            low[u] = min(low[u], dfn[v]);
        }   
    }
}

signed main() {
    while (cin >> n >> m && n) {
        memset (dfn, 0, sizeof dfn);
        memset (head, 0, sizeof head);
        memset (bridge, 0, sizeof bridge);
        tot = 1, tim = 0;
        int pre = 1e9;
        for (int i = 1; i <= m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            add_edge(u, v, w), add_edge(v, u, w);
        }
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (!dfn[i])
                cnt++, tarjan(i, 0);
        }
        if (cnt >= 2) {
            cout << "0\n";
        } else {
            for (int j = 2; j <= tot; j += 2) {
                if (bridge[j])
                    pre = min(pre, edges[j].w);
            }
            if (pre == 1e9)
                cout << "-1\n";
            else if (pre == 0)
                cout << 1 << '\n';
            else
                cout << pre << '\n';
        }
    }
    return 0;
}

割边（桥）定义

对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。

实现步骤

跟割点没差什么，不用考虑根节点问题，只要改成 low_v > dfn_u 即可。

U132350 【模板】割边（桥）

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, m, dfn[N], low[N], tim, root, cnt;
bool vis[N];
vector<int> nbr[N];

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++tim;
    for (int v : nbr[u]) {
        if (v == fa)
            continue;
        if (!dfn[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                cnt++;
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        nbr[u].push_back(v);
        nbr[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i])
            tarjan(i, 0);
    }
    cout << cnt;
    return 0;
}