社区讨论

vector建图如何去重边?

P2860[USACO06JAN] Redundant Paths G参与者 7已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@mhjl0f3m
此快照首次捕获于
2025/11/04 04:17
4 个月前
此快照最后确认于
2025/11/04 04:17
4 个月前
查看原帖
Rt.
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=500005,M=4000005;
int n,m,dfncnt,dfn[N],low[N],inst[N],st[M],stot,root,bcccnt;
vector<int>R[N];
vector<int>bcc[N];
void tarjan(int u)
{
	dfn[u]=low[u]=++dfncnt,
	st[++stot]=u,inst[u]=1;
	if(u==root&&(!R[u].size()))
	{
		bcc[++bcccnt].push_back(u);
		return ;
	}
	for(auto v:R[u])
	{
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				++bcccnt;
				while(st[stot+1]!=v)
					bcc[bcccnt].push_back(st[stot--]);
				bcc[bcccnt].push_back(u);
			}
		}else if(inst[v]&&)
			low[u]=min(low[u],dfn[v]);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(x==y) continue;
		R[x].push_back(y);
		R[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) root=i,tarjan(i);
	printf("%d\n",bcccnt);
	for(int i=1;i<=bcccnt;i++)
	{
		printf("%d ",bcc[i].size());
		for(auto v:bcc[i])
			printf("%d ",v);
		printf("\n");			
	}
	return 0;
}
91分

回复

9 条回复,欢迎继续交流。

正在加载回复...