社区讨论

似乎与重边有关,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 条回复,欢迎继续交流。

正在加载回复...