边双85pts
查看原帖
边双85pts
243672
する楼主2022/10/27 08:32
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int dfn[N],low[N],n,m,root,cnt,cnnt;
map<int,bool> mp[N];
vector<int> nbr[N],v[N];
bool vis[N];
void tarjan(int x,int fa)
{
	low[x]=dfn[x]=++cnt;
	for(int i=0;i<nbr[x].size();i++)
	{
		int y=nbr[x][i];
		if (y == fa) continue;
		if(dfn[y]==0)
		{
			tarjan(y,x);
			low[x]=min(low[x],low[y]);
			if(low[y]>dfn[x])
				mp[x][y]=1,mp[y][x]=1;
		}
		else if(y!=fa)
			low[x]=min(low[x],dfn[y]);
	}
}
void dfs(int x)
{
	v[cnnt].push_back(x);
	vis[x]=1;
	for(int i=0;i<nbr[x].size();i++)
	{
		int y=nbr[x][i];
		if(vis[y]==0&&mp[x][y]==0)
			dfs(y);
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		nbr[u].push_back(v);
		nbr[v].push_back(u);
	}
	for(root=1;root<=n;root++)
		if(dfn[root]==0)
			tarjan(root,0);
	for(int i=1;i<=n;i++)
		if(vis[i]==0)
		{
			cnnt++;
			dfs(i);
		}
	cout<<cnnt<<endl;
	for(int i=1;i<=cnnt;i++)
	{
		cout<<v[i].size()<<" ";
		for(int k=0;k<v[i].size();k++)
			cout<<v[i][k]<<" ";
		puts("");
	}
	return 0;
}
2022/10/27 08:32
加载中...