0puts,不知如何调

P8436 【模板】边双连通分量

zhouyujie @ 2022-12-18 11:34:26

代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
vector<int> ans[MAXN];
int dfn[MAXN], low[MAXN], visited[MAXN]; 
int head[MAXN], ver[MAXN * 2], Next[MAXN * 2];
int num = 0;
int root, dcc, tot;
bool bridge[MAXN];
void add(int x, int y) {
    ver[++tot] = y;
    Next[tot] = head[x];
    head[x] = tot;
}
void tarjan(int i, int in_edge) {
    dfn[i] = low[i] = ++num;
    for(int j = head[i]; j ; j = Next[j]) {
        int v = ver[j];
        if(!dfn[v]) {
            tarjan(v, j);
            low[i] = min(low[i], low[v]);
            if(low[v] > dfn[i]) {
                bridge[i] = bridge[i ^ 1] = true;
            }
        }else if(i != (in_edge ^ 1)) low[i] = min(low[i], dfn[v]);
    }
}
void dfs(int i) {
    visited[i] = dcc;
    if(i) ans[dcc].push_back(i);
    for(int j = head[i]; j ; j = Next[j]) {
        int v = ver[j];
        if(visited[v] || bridge[j]) continue;
        dfs(v);
    }
}
int main() {
    int n, e;
    cin >> n >> e;
    for(int i = 1; i <= e; i++) {
        int u, v;
        cin >> u >> v;
        if(u == v) continue;
        add(u, v);
        add(v, u);
    }
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) {
            root = i;
            tarjan(i, 0);
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!visited[i]) {
            ++dcc;
            dfs(i);
        }
    }
    cout << dcc << endl;
    for(int i = 1; i <= dcc; i++) {
        cout << ans[i].size() << " ";
        for(int j = 0; j < ans[i].size(); j++) {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

测试结果


by zhouyujie @ 2022-12-18 11:35:10

其实样例#3,#4就过不了,求大佬帮助。


by fdszlzl @ 2022-12-18 12:34:31

bridge[i] = bridge[i ^ 1] = true;

所以tot要从1开始,不然对不上


by zhouyujie @ 2022-12-19 15:27:25

@fdszlz 能说的详细一点吗?本蒟蒻还是不懂。。。


by lyc1001 @ 2023-01-07 20:37:23

@zhouyujie 月度考古。亦或的作用是找到并标记这条边的反向边,用手模拟一下,1^1=0,2^1=3,如果第一条边是1号,那他的反向边就是2,但亦或之后得出0,,会出锅,而如果改成2号,反向边就是3,2^1刚好是3,就没问题了


|