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,就没问题了