连通性相关问题题解

[P2341 USACO03FALL / HAOI2006] 受欢迎的牛 G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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

using namespace std;

const int N = 1e4 + 10;

vector<int> g[N];
int n, timestamp;
int dfn[N], low[N];
stack<int> stk;
bool in_stk[N];
int id[N], si[N], scc_cnt;
int dout[N];

void tarjan(int u) {
    dfn[u] = low[u] = ++ timestamp;
    stk.push(u);
    in_stk[u] = true;

    for (auto v : g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        int y;
        scc_cnt ++;
        do {
            y = stk.top();
            stk.pop();
            in_stk[y] = false;
            id[y] = scc_cnt;
            si[scc_cnt] ++;
        } while (y != u);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    while (m -- ) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
    }

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

    // 缩点
    for (int i = 1; i <= n; i ++ ) {
        for (auto v: g[i]) {
            int a = id[i], b = id[v];
            if (a != b) {
                dout[a] ++;
            }
        }
    }

    int sum = 0, zeros = 0;
    for (int i = 1; i <= scc_cnt; i ++ ) {
        if (!dout[i]) {
            sum = si[i];
            zeros ++;
            if (zeros > 1) {
                sum = 0;
                break;
            }
        }
    }

    cout << sum << endl;

    return 0;
}

[P2860 USACO06JAN] Redundant Paths G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <bits/stdc++.h>

using namespace std;

const int N = 5010, M = 2e4 + 10;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
bool is_brige[M];
int id[N], stk[N], top;

int du[N];
int dcc_cnt;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void tarjan(int u, int from) { // u 是当前节点，from是来的边的id
    dfn[u] = low[u] = ++ timestamp;
    stk[++ top] = u;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if (dfn[u] < low[j]) {
                is_brige[i] = is_brige[i ^ 1] = true;   // i ^ 1 是另一条边， 标记一正一反两条边为桥
            }
        } else if (i != (from ^ 1)) {
            low[u] = min(low[u], dfn[j]);
        }
    }

    if (low[u] == dfn[u]) {
        int y;
        dcc_cnt ++;
        do {
            y = stk[top --];
            id[y] = dcc_cnt;
        } while (y != u);
    }
}

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

    memset(h, -1, sizeof(h));
    while (m --) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }

    tarjan(1, -1);

    for (int i = 1; i <= n; i ++ ) {
        for (int j = h[i]; ~j; j = ne[j]) {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b) {
                du[a] ++;
            }
        }
    }

    int cnt = 0;
    for (int i = 1; i <= dcc_cnt; i ++ ) {
        if (du[i] == 1) cnt ++;
    }

    cout << (cnt + 1) / 2 << '\n';

}

[P3225 HNOI2012] 矿场搭建 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

• 对于一个点双连通分量来说，只需要任意选取两个点作为出口

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

using namespace std;

typedef unsigned long long ULL;

const int N = 1010, M = 510;

int n, m, T;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool cut[N];
vector<int> dcc[N];
int id[N], dcc_cnt;
int root;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++ timestamp;
    stk[++ top] = u;

    if (u == root && h[u] == -1) {
        dcc_cnt ++;
        dcc[dcc_cnt].push_back(u);
        return;
    }

    int cnt = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
            if (dfn[u] <= low[j]) {
                cnt ++;
                if (u != root || cnt > 1) cut[u] = true;
                dcc_cnt ++;
                int y;
                do {
                    y = stk[top --];
                    dcc[dcc_cnt].push_back(y);
                } while (y != j);
                dcc[dcc_cnt].push_back(u);
            }
        }
        else low[u] = min(low[u], dfn[j]);
    }
}

int main() {
    T = 1;
    while (cin >> m, m) {
        for (int i = 1; i <= n; i ++ ) dcc[i].clear();
        idx = timestamp = top = dcc_cnt = n = 0;
        memset(h, -1, sizeof h);
        memset(dfn, 0, sizeof dfn);
        memset(cut, 0, sizeof cut);

        while (m --) {
            int a, b;
            cin >> a >> b;
            n = max(n, max(a, b));
            add(a, b), add(b, a);
        }

        for (root = 1; root <= n; root ++ )
            if (!dfn[root])
                tarjan(root);

        int res = 0;
        ULL sum = 1;
        for (int i = 1; i <= dcc_cnt; i ++ ) {
            int cnt = 0;
            for (int j = 0; j < dcc[i].size(); j ++ )
                if (cut[dcc[i][j]])
                    cnt ++;
            if (cnt == 0) {
                if (dcc[i].size() == 1) res ++;
                else res += 2, sum *= dcc[i].size() * (dcc[i].size() - 1) / 2;
            }
            else if (cnt == 1) res += 1, sum *= dcc[i].size() - 1;
        }

        printf("Case %d: %d %llu\n", T, res, sum);
        T ++;
    }

    return 0;
}