记录编号	47715	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺四]晨跑路径	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2012-11-02 23:03:38	内存使用	0.38 MiB

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=2022;
vector<int> map[MAXN];
int N,M,top=0,GD[MAXN],Index=0;
int dfn[MAXN]={0},low[MAXN]={0},ansnum=0;
int cut[MAXN]={0},Root=1,flag[MAXN],ans[MAXN];
inline void init()
{
	scanf("%d%d",&N,&M);int x,y;
	for(int i=1;i<=M;i++)
	{
		scanf("%d%d",&x,&y);
		map[x].push_back(y);
		map[y].push_back(x);
	}
}
inline int Min(int a,int b){return a<b?a:b;}
void dfs(int k,int pnt)
{
	Index++;dfn[k]=Index,low[k]=Index;
	int v,tch=0;
	for(unsigned int i=0;i<map[k].size();i++)
	{
		v=map[k][i]; if(v==pnt) continue;
		if(dfn[v])low[k]=Min(low[k],dfn[v]);
		else 
		{
			tch++;dfs(v,k);
			low[k]=Min(low[k],low[v]);
			if((k==Root&&tch>1)||(k!=Root&&low[v]>=dfn[k]))
				cut[k]=1;
		}
	}
}
int canuse;
void dfs2(int k)
{
	flag[k]=1;
	for(unsigned int i=0;i<map[k].size();i++)
		if((!flag[map[k][i]]) && (map[k][i]!=canuse)) 
			dfs2(map[k][i]);
}

int main()
{
	freopen("running.in","r",stdin);
	freopen("running.out","w",stdout);
	init();  dfs(1,0);
	for(int i=2;i<=N-1;i++)
	{
		if(!cut[i]) continue;
		memset(flag,0,sizeof(flag));
		canuse=i;	dfs2(1); 
		if(!flag[N]){ansnum++;ans[ansnum]=i;}
	}
	printf("%d\n",ansnum);
	for(int i=1;i<=ansnum;i++) 
		printf("%d ",ans[i]);
	return 0;
}