边双板子求调50pts

P8436 【模板】边双连通分量

PassName @ 2024-10-01 15:28:10

RT,看到题解区说可以仿照求强联通分量的办法求边双就试了试,但是会WA掉一些点。不知道是哪里的问题

#include <bits/stdc++.h>

#define int long long
#define rint register int
#define endl '\n'

using namespace std;

const int N = 5e6 + 5;
const int M = 1e7 + 5;

int n, m;
int h[N], e[M], ne[M], idx; 
int dfn[N], low[N], c[N];
int num, cnt, top;
bool ins[N];
int stk[N];
vector<int> ans[N];

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

void tarjan(int x, int father)
{
    dfn[x] = low[x] = ++num;
    stk[++top] = x;
    for (rint i = h[x]; i; i = ne[i])
    {
        int y = e[i];
        if (y == father) continue;
        if (!dfn[y])
        {
            tarjan(y, x);
            low[x] = min(low[x], low[y]);
        }
        else if (ins[y]) low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x])
    {
        cnt++; int y;
        do
        {
            y = stk[top--], ins[y] = 0;
            c[y] = cnt, ans[cnt].push_back(y);
        } while (x != y);
    }
}

signed main()
{
    cin >> n >> m;
    for (rint i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    for (rint i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i, 0);
    cout << cnt << endl;
    for (rint i = 1; i <= cnt; i++)
    {
        cout << ans[i].size() << " ";
        for (rint j : ans[i]) cout << j << " ";
        cout << endl;
    }
    return 0;
}

by lrx___ @ 2024-10-02 07:42:52

似乎没有标记 ins_x=1


by PassName @ 2024-10-02 10:11:19

@lrx___ 加上也过不了,重边自环没处理,没事了


|