记录编号	47651	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺四]晨跑路径	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.053 s
提交时间	2012-11-02 18:54:41	内存使用	3.30 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
using namespace std;

int ava,ptop[2010],wayto[16010],waynext[16010];
int n,total,ind,tim[2010],timlow[2010];
bool ok,visited[2010],ans[2010];

void putway(int pos,int to)
{
	if (!ptop[pos])
	{
		ava++;
		ptop[pos]=ava;
		wayto[ava]=to;
	}
	else
	{
		int poi;
		poi=ptop[pos];
		while (waynext[poi])
			poi=waynext[poi];
		ava++;
		waynext[poi]=ava;
		wayto[ava]=to;
	}
}

void tarjan(int pos,int lastpos)
{
	ind++;
	tim[pos]=ind;
	timlow[pos]=ind;
	int poi,to;
	poi=ptop[pos];
	while (poi)
	{
		to=wayto[poi];
		if (tim[to]==0)
		{
			tarjan(to,pos);
			timlow[pos]=min(timlow[pos],timlow[to]);
			if(timlow[to]>=tim[pos])
			{
				if (pos!=1&&pos!=n)
				{
					if (!ans[pos])
					{
						total++;
						ans[pos]=true;
					}
				}
			}
		}
		else if (to!=lastpos)
		{
			timlow[pos]=min(timlow[pos],tim[to]);
		}
		poi=waynext[poi];
	}
}

void dfs(int pos)
{
	visited[pos]=true;
	if (pos==n)
		ok=true;
	int poi,to;
	poi=ptop[pos];
	while (poi)
	{
		to=wayto[poi];
		if (!visited[to])
		{
			dfs(to);
			if (ok)
				return;
		}
		poi=waynext[poi];
	}
}

int main(void)
{
	freopen("running.in","r",stdin);
	freopen("running.out","w",stdout);
	int i,m,a,b;
	cin>>n>>m;
	for (i=1;i<=m;i++)
	{
		cin>>a>>b;
		putway(a,b);
		putway(b,a);
	}
	tarjan(1,0);
	for (i=2;i<n;i++)
		if (ans[i])
		{
			ok=false;
			memset(visited,0,sizeof(visited));
			visited[i]=true;
			dfs(1);
			if (ok)
			{
				total--;
				ans[i]=false;
			}
		}
	cout<<total<<endl;
	a=0;
	for (i=2;i<n;i++)
		if (ans[i])
		{
			if (a)
			{
				cout<<' '<<i;
			}
			else
			{
				a=1;
				cout<<i;
			}
		}
	if (a)
		cout<<endl;
	return(0);
}