社区讨论
似乎与重边有关,WA了不少数据点
P8436【模板】边双连通分量参与者 5已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @m2nlf2yh
- 此快照首次捕获于
- 2024/10/25 01:44 去年
- 此快照最后确认于
- 2024/10/25 10:45 去年
没判重,不知道要判什么重和怎么判重
CPP#include<bits/stdc++.h>
using namespace std;
int n,m,ut,vt,wt,dfn[100010],low[500010],cnt,cntbcc;
vector<int> g[500010];
bool iscut[500010],isnonezerolow[500010];
vector<int> cut;
vector<int> bcc[500010];
void tarjan(int u,int fa) {
for (int i = 1;i <= n;i ++)
printf("low[%d]=%d dfn[%d]=%d\n",i,low[i],i,dfn[i]);
printf("u=%d fa=%d\n",u,fa);
low[u] = dfn[u] = ++cnt;
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]);
} else if (v != fa) low[u] = min(low[u],dfn[v]);
}
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);
for (int i = 1;i <= n;i ++) {
bcc[low[i]].push_back(i);
if (!isnonezerolow[low[i]]) ++ cntbcc;
isnonezerolow[low[i]] = true;
}
printf("%d\n",cntbcc);
for (int i = 1;i <= cnt;i ++) {
if (!isnonezerolow[i]) continue;
printf("%d ",bcc[i].size());
for (int j = 0;j < bcc[i].size();j ++)
printf("%d ",bcc[i][j]);
printf("\n");
}
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...