边双板子求调50pts
查看原帖
边双板子求调50pts
524911
PassName楼主2024/10/1 15:28

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;
}
2024/10/1 15:28
加载中...