玄关求条
查看原帖
玄关求条
959481
niusitu楼主2024/11/26 20:58

实在是不知道哪里的问题,向dl指教

#include<bits/stdc++.h>
#define I return 
#define love 0
#define DLY ;
using namespace std;
const int maxn=1000010,maxm=5000010;
int head[maxn],nxt[maxm<<1],to[maxm<<1],tot=1;
void add(int x,int y)
{
	if (x==y) return ; 
	to[++tot]=y;nxt[tot]=head[x];head[x]=tot;
}
int n,m;
int dfn[maxn],low[maxn],times=0;
int cut[maxn],root;
int dcc_cut;
int top,st[maxn];
vector<int> dcc[maxn<<1];
void tarjan(int x)
{
	dfn[x]=low[x]=++times;
	st[++top]=x;
	if (x==root&&head[x]==0)
	{
		dcc[dcc_cut++].push_back(x);
		return ;
	}
	for (int i=head[x];i;i=nxt[x])
	{
		int y=to[i];
		if (!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
			if (dfn[x]<=low[y])
			{
				dcc_cut++;
				int v;
				do
				{
					v=st[top--];
					dcc[dcc_cut].push_back(v);
				}while(v!=y);
				dcc[dcc_cut].push_back(x);
			}
		}
		else
		{
			low[x]=min(low[x],dfn[y]);
		}
	}
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	
	for (register int i=1;i<=m;++i)
	{
		int x,y;
		cin>>x>>y;
		//if (x==y) continue;
		add(x,y);
		add(y,x);
	}
	for (register int i=1;i<=n;++i)
	{
		if (!dfn[i])
		{
			root=i;
			tarjan(i);
		}
		
	}
	cout<<dcc_cut<<'\n';
	for (register int i=1;i<=dcc_cut;++i)
	{
		cout<<dcc[i].size();
		for (register int j=0;j<dcc[i].size();++j)
		{
			cout<<' '<<dcc[i][j];
		}
		cout<<"\n";
	}
	I love DLY
	/*
	5 3
	1 2
	2 3	
	1 3
	*/
}
2024/11/26 20:58
加载中...