# 76分求助,4,6,11wa
查看原帖
# 76分求助,4,6,11wa
301191
tle_wa楼主2022/10/19 21:32
 #include<bits/stdc++.h>
using namespace std;

bool flag[100007];
int n,m,root,ans=0;
int num[100007]/*自己的时间戳*/,low[100007]/*不经过父节点能到的最大时间戳*/,sjc; 

int head[100007],cnt=0;
struct node
{
	int to,next;
}h[200007];
void add(int u,int v)
{
	h[++cnt].next=head[u];
	h[cnt].to=v;
	head[u]=cnt;
}

int father[100007];
void init()
{
	for(int i=1;i<=n;i++)
		father[i]=i;
}
int find(int x)
{
    while(x!=father[x])
		x=father[x]=father[father[x]];
    return x;
}
void merge(int u,int v)
{
	int t1,t2;
	t1=find(u);
	t2=find(v);
	if(t1>t2)
		swap(t1,t2);
	if(t1!=t2)
		father[t2]=t1;
} 

void dfs(int cur,int fa)
{
	int child=0;//当前顶点cur儿子个数 
	++sjc;
	num[cur]=sjc;
	low[cur]=sjc;
	
	for(int i=head[cur];i>0;i=h[i].next)
	{
		int zi=h[i].to;
		if(num[zi]==0)//还没有被访问
		{
			child++;
			dfs(zi,cur);
			low[cur]=min(low[cur],low[zi]); 
			if(cur!=root && low[zi]>=num[cur])//至少存在一个孩子i使其能达到的最小时间戳在cur后 
				flag[cur]=true,ans++;
			if(cur==root && child==2)//如果是根节点并在当前生成树中有两个孩子 
				flag[cur]=true,ans++; 
		} 
		else if(zi!=fa)//曾经被访问过,且i不是cur的父节点 --> i为cur的祖先,更新最小时间戳 
			low[cur]=min(low[cur],num[zi]); 
	}
}

int main()
{
	cin>>n>>m;
	init();
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		add(a,b);
		add(b,a);
		merge(a,b);//并查集 
	}
	
	
	for(int i=1;i<=n;i++)
	{
		if(father[i]==i)
		{
			root=i;
			dfs(root,root);
		}
	}
	
	cout<<ans<<endl;
	for(int i=1;i<=n;i++)
		if(flag[i]==true)
			printf("%d ",i); 
	return 0;
} 
2022/10/19 21:32
加载中...