社区讨论

why 48pts?

P8435【模板】点双连通分量参与者 2已保存回复 1

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@mhk2jrk0
此快照首次捕获于
2025/11/04 12:28
4 个月前
此快照最后确认于
2025/11/04 12:28
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=500010,M=2000010;
vector<int> g[N];
int tot,dfn[N],low[N],root,cnt;
bool cut[N];
stack<int>s;
vector<int> res[N];
void tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	s.push(x);
	int i,j,y,child=0,z;
	if(g[x].size()==0)
	{
		res[++cnt].push_back(x);
	}
	for(i=0;i<g[x].size();i++)
	{
		y=g[x][i];
		if(!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x])
			{
				child++;
				if(child>=2||x!=root) cut[x]=1;
				cnt++;
				while(1)
				{
					z=s.top();
					s.pop();
					res[cnt].push_back(z);
					if(z==y) break;
				}
			}
			res[cnt].push_back(x);
		}
		else low[x]=min(low[x],dfn[y]);
	}
}
int main()
{
	int n,m,i,j,u,v;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		if(u==v) continue;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(i=1;i<=n;i++)
		if(!dfn[i])
		{
			while(s.size()) s.pop(); 
			root=i;
			tarjan(i);
		}
	printf("%d\n",cnt);
	for(i=1;i<=cnt;i++)
	{
		printf("%d ",res[i].size());
		for(j=0;j<res[i].size();j++)
			printf("%d ",res[i][j]);
		printf("\n");
	 } 
	return 0;
}

回复

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

正在加载回复...