为什么只有44分?
查看原帖
为什么只有44分?
137491
wangjunze楼主2020/8/6 23:20
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
using namespace std;

const int Maxn=2e4+7;
const int SIZE=1e5+7;
const int INF=0x3f3f3f3f;
int n,m,cnt,ind;
int head[Maxn],dfn[Maxn],low[Maxn];
vector<int> ans;
struct Edges
{
	int to;int next;	
}e[2*SIZE];

void addedge(int x,int y)
{
	e[cnt].to=y;
	e[cnt].next=head[x];
	head[x]=cnt++;
}

inline int read()
{
	int x=0,f=1;
	char ch;
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return f*x; 
}

void dfs(int par,int x)
{
	dfn[x]=low[x]=++ind;
	int child=0;
	for(int i=head[x];~i;i=e[i].next)
	{
		int cur=e[i].to;
		if(!dfn[cur])
		{
			dfs(par,cur);
			low[x]=min(low[x],low[cur]);
			if(low[cur]>=dfn[x] && par!=x)ans.push_back(x);
			if(par==x)child++;
		}
		low[x]=min(low[x],dfn[cur]);
	}
	if(child>=2 && par==x)ans.push_back(x);
}

int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	n=read();m=read();
	memset(head,-1,sizeof(head));
	REP(i,m)
	{
		int x,y;
		x=read(),y=read();
		x--,y--;
		addedge(x,y);
		addedge(y,x);
	}
	REP(i,n)if(!dfn[i])dfs(i,i);
	cout<<ans.size()<<endl;
	for(int u:ans)
		cout<<u+1<<" ";
	cout<<endl;
	return 0;
}

2020/8/6 23:20
加载中...