蒟蒻新学双连通分量,求条
查看原帖
蒟蒻新学双连通分量,求条
1065071
Atserckcn楼主2024/8/9 22:11

上次在边双就发了一个

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,M=2e6+5;
int head[N],cnt_e,n,m,u,v,cnt_bcc,low[N],dfn[N],idx;
stack<int> st;
vector<int> ans[N];
struct E{
	int from,to,pre;
}e[M<<1];
void add(int from,int to)
{
	e[++cnt_e].from=from;
	e[cnt_e].to=to;
	e[cnt_e].pre=head[from];
	head[from]=cnt_e;
	return;
}
void dfs(int u,int fa)
{
	low[u]=dfn[u]=++idx;
	int son=0;
	st.push(u);
	for(int i=head[u];i;i=e[i].pre)
	{
		int v=e[i].to;
		if(v==fa)continue;
		if(!dfn[v])
		{
			++son;
			dfs(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				++cnt_bcc;
				int t=-1;
				do{
					t=st.top();st.pop();
					ans[cnt_bcc].push_back(t);
				}while(t!=u);
			}
		}
		else
			low[u]=min(low[u],dfn[v]);
	}
	if(fa==0&&son==0)
		ans[++cnt_bcc].push_back(u);
	return;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
		{
			while(!st.empty())
				st.pop();
			dfs(i,0);
		}
	}
	printf("%d\n",cnt_bcc);
	for(int i=1;i<=cnt_bcc;i++)
	{
		printf("%d ",ans[i].size());
		for(auto j:ans[i])
			printf("%d ",j);
		putchar('\n');
	}
	return 0;
}

https://www.luogu.com.cn/record/171695885

2024/8/9 22:11
加载中...