记录编号	69569	评测结果	AAAAAAAAAA
题目名称	[金陵中学2007] 传话	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2013-09-18 17:19:33	内存使用	1.29 MiB

#include <fstream>
#include <vector>
using namespace std;
ifstream fi("messagez.in");
ofstream fo("messagez.out");
bool g[1001][1001],f[1001];
int a[1001],t,s=0,num[1001],n,m;
vector <int> v[1001];
void init()
{
	int i,j,a,b;
	fi>>n>>m;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			g[i][j]=false;
	for (i=1;i<=n;i++) f[i]=true;
	for (i=1;i<=m;i++)
	{
		fi>>a>>b;
		g[a][b]=true;
	}
	t=n;
}
void dfs1(int u)
{
	int r;
	f[u]=false;
	for (r=1;r<=n;r++)
		if (f[r]&&g[u][r])
			dfs1(r);
	a[t--]=u;
}
void dfs2(int u)
{
	int r;
	f[u]=false;v[s].push_back(u);num[u]=s;
	for (r=1;r<=n;r++)
		if (f[r]&&g[r][u]) dfs2(r);
}
int main()
{
	int i,j;
	init();
	for (i=1;i<=n;i++)
		if (f[i]) dfs1(i);
	for (i=1;i<=n;i++) f[i]=true;
	for (i=1;i<=n;i++)
		if (f[a[i]])
		{
			s++;
			dfs2(a[i]);
		}
	for (i=1;i<=n;i++)
		if (v[num[i]].size()==1) fo<<"F"<<endl;else fo<<"T"<<endl;
	return 0;
}