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
似乎没有标记
by PassName @ 2024-10-02 10:11:19
@lrx___ 加上也过不了,重边自环没处理,没事了