WA了一个点,本蒟蒻已经WA傻了,求助大佬
查看原帖
WA了一个点,本蒟蒻已经WA傻了,求助大佬
397926
愚末语tenseTL楼主2021/1/12 19:22
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define pub push_back
#define pob pop_buck
const int N= 2e4+5;
bool s[N];
vector<int> G[N];
set<int> ap;
int prenum[N],parent[N],lowest[N],color[N],times,n,m;
int t;
void dfs(int current,int pre)
{
	prenum[current]=lowest[current]=times;
	times++;
	color[current]=1;
	for(int i=0;i<G[current].size();i++)
	{
		int next=G[current][i];
		if(color[next]==0)
		{
			parent[next]=current;
			dfs(next,current);
			lowest[current]=min(lowest[current],lowest[next]);
		}
		else if(next!=pre) 
		{
			lowest[current]=min(lowest[current],prenum[next]);
		}
	}
}
void art_point()
{
	for(int i=1;i<=n;i++)color[i]=0;
	times=1;
	dfs(t,0);
	int np=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]==0)continue;
		int p=parent[i];
		if(p==0)continue;
		if(p==t)np++;
		else if(prenum[p]<=lowest[i])ap.insert(p);
	}
	if(np>1)ap.insert(t);
	cout<<ap.size()<<endl;
	for(auto it=ap.begin();it!=ap.end();it++)
	{
		cout<<*it<<' ';
	}
	cout<<endl; 
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		G[a].pub(b);	
		G[b].pub(a);
		s[b]=1;
		s[a]=1;
		t=a; 
	}
	art_point();
	return 0;
 } 
2021/1/12 19:22
加载中...