重边怎么处理?

LinearXeno @ 2024-10-25 21:13:34

#include<bits/stdc++.h>
using namespace std;
int n,m,ut,vt,wt,dfn[1000010],low[1000010],cnt,cntbcc;
vector<int> g[1000010];
vector<int> bcc[1000010];
stack<int> s;
void tarjan(int u,int fa) {
    dfn[u] = low[u] = ++cnt;
    s.push(u);
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i];
        if (!dfn[v]) {
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
            //if (low[v] > dfn[u]) bridge.push_back(make_pair(u,v));//
        } else if (v != fa) low[u] = min(low[u],dfn[v]);
    }
    if (low[u] == dfn[u]) {
        ++ cntbcc;
        while (s.top() != u) {
            bcc[cntbcc].push_back(s.top());
            s.pop();
        }
        bcc[cntbcc].push_back(s.top());
        s.pop();
    }
    return;
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i = 1;i <= m;i ++) {
        scanf("%d%d",&ut,&vt);
        g[ut].push_back(vt);
        g[vt].push_back(ut);
    }
    for (int i = 1;i <= n;i ++)
        if (!dfn[i]) tarjan(i,0);
    printf("%d\n",cntbcc);
    for (int i = 1;i <= cntbcc;i ++) {
        printf("%d ",bcc[i].size());
        for (int j = 0;j < bcc[i].size();j ++)
            printf("%d ",bcc[i][j]);
        printf("\n");
    }
    return 0;
}

by FanMingxuan @ 2024-10-25 21:15:20

在你的 tarjan 函数参数传一个来自哪条边，然后利用 x ^ 1 = y 的奇偶边的小技巧判断是不是回去了

by FanMingxuan @ 2024-10-25 21:17:15

使用vector的话，就记录一个pair，存一下终点和边的编号就行 @LinearXeno

by FanMingxuan @ 2024-10-25 21:18:56

比如第 i 条边，给 u 放一个 {v,i << 1} ，给 v 放一个 {u,i << 1 | 1}

by LinearXeno @ 2024-10-25 21:27:31

@FanMingxuan 请问奇偶边技巧有文章或者链接吗

by Vector_Li @ 2024-10-29 21:49:59

@LinearXeno 如果用 vector 存图，可以加一个变量记录一下，具体看代码（实现是 0 下标，https://judge.yosupo.jp/problem/two_edge_connected_components 的代码）：

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

using namespace std;

const int N = (int) 2E5;

int n, m;
vector<int> e[N];

int p[N];
int d[N], f[N], x;
stack<int> s;

int t[N], c;
vector<int> a[N];

void DFS(int u) {
    d[u] = x;
    x = x + 1;
    f[u] = d[u];
    s.push(u);

    int o = 0;
    for (auto v : e[u]) {
        if (v == p[u] && o == 0) {
            o = 1;
            continue;
        }
        if (d[v] < 0) {
            p[v] = u;
            DFS(v);
            f[u] = min(f[u], f[v]);
        } else {
            f[u] = min(f[u], d[v]);
        }
    }

    if (f[u] == d[u]) {
        while (s.top() != u) {
            t[s.top()] = c;
            a[c].push_back(s.top());
            s.pop();
        }
        t[s.top()] = c;
        a[c].push_back(s.top());
        s.pop();
        c = c + 1;
    }
}

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

    fill(d, d + n, 0 - 1);
    for (int u = 0; u < n; u++) {
        if (d[u] < 0) {
            p[u] = 0 - 1;
            DFS(u);
        }
    }

//  for (int u = 0; u < n; u++) {
//      cout << p[u] << " " << f[u] << "\n";
//  }

    cout << c << "\n";
    for (int i = 0; i < c; i++) {
        cout << (int) a[i].size() << " ";
        for (auto u : a[i]) {
            cout << u << " ";
        }
        cout << "\n";
    }
}

int main() {
#ifdef LOCAL
    freopen("A.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int t;
    t = 1;
    for (int i = 0; i < t; i++) {
        solve();
    }
    return 0;
}

by LinearXeno @ 2024-10-30 01:02:58

@FanMingxuan 搞懂了谢谢