题解 | #Redundant Paths#

为什么这篇没人写题解呢，去网上查了半天找到的还大多数是链式前向星建图的。 这题应该算是一个边双连通分量的板子吧，我们首先进行点双连通分量缩点，缩点后的图是一片森林，如果原图连通那么就是一棵树，若想整张图点双连通我们记所有度为的点个数为，最少添加的边数为但我们发现tarjan跑有向图一点问题都没有，跑无向图时可能会走回头路，所以我们使用一个神奇的操作，即异或上一个1的操作，我们把正边记为，反边记为这样判断的时候就可以判断这条边是否走过。具体实现看代码有什么问题欢迎大家私聊讨论

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

std::stack<int> st;
std::vector<std::pair<int, int> > e[500005];
std::vector<std::vector<int> > ans;
int dfn[500005], low[500005], vis[500005], col[500005], du[500005];
int cnt = 0, num = 0;

void tarjan(int u, int f) {
    dfn[u] = low[u] = ++ cnt;
    vis[u] = 1;
    st.push(u);

    for (auto [v, las] : e[u]) {
        if (las == (f ^ 1)) continue;//这里即为判断该边是否走过
        if (!dfn[v]) {
            tarjan(v, las);
            low[u] = std::min(low[u], low[v]);
        }
        else {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    
    if (dfn[u] == low[u]) {
        std::vector<int> vec;
        num++;
        while (1) {
            int cur = st.top();
            vec.push_back(cur);
            st.pop();
            col[cur] = num;
            vis[cur] = 0;
            if (cur == u) break;
        }
        ans.push_back(vec);
    }
}

void solve() {
    int n, m;
    std::cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        std::cin >> u >> v;
        e[u].push_back({v, i << 1});
        e[v].push_back({u, i << 1 | 1});
    }

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

    for (int i = 1; i <= n; i++) {
        for (auto [v, lat] : e[i]) {
            int x = col[i], y = col[v];
            if (x != y) {
                du[y]++;//由于是无向图，如果给两个点的度都加一的话“叶子”节点的度就为2了，所以我这里只给y加了一个度。
            }
        }
    }

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

    std::cout << (ans + 1) / 2 << '\n';
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}