记录编号	69417	评测结果	AAAAAAAAAA
题目名称	[金陵中学2007] 传话	最终得分	100
用户昵称	老师好~~~	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2013-09-15 11:53:18	内存使用	4.17 MiB

#include<fstream>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
ifstream fin("messagez.in");
ofstream fout("messagez.out");
int a[1001][1001],color[1001],t[1001],f[1001];//t数组与f数组分别记录图中结点变灰与变黑的时间
int n,m,shijian=0;
int flag[1001];
int ans[1001];
int K=1;
int temp;
class woca
{
public:
	int x;
	int y;
}b[1001];
bool compare(woca n,woca m)
{
	if(n.y>m.y)
		return 1;
	else
		return 0;
}
void dfs(int x)//第一遍深搜把时间戳搞出来
{
	color[x]=1;t[x]=++shijian;
	for(int i=1;i<=n;i++)
	{
		if(a[x][i]==1&&color[i]==0)//只搜白色顶点
			dfs(i);
	}
	color[x]=2;f[x]=++shijian;
}
void SCC(int x)//第二次深搜求强联通分量
{
	flag[x]=temp;
	for(int i=1;i<=n;i++)
	{
		if(a[i][x]==1&&flag[i]==0)
		{
			K++;
			SCC(i);
		}
	}
}
int main()
{
	int A,B;
	fin>>n>>m;
	int i,j;
	for(i=1;i<=m;i++)
	{
		fin>>A>>B;
		a[A][B]=1;
	}
	for(i=1;i<=n;i++)
	{
		if(color[i]==0)
			dfs(i);
	}
	for(i=1;i<=n;i++)
	{
		b[i].x=i;
		b[i].y=f[i];
	}
	sort(b+1,b+n+1,compare);
	for(i=1;i<=n;i++)
	{
		temp=b[i].x;
		if(ans[b[i].x]==0)
		{                  //深搜时经历了哪些点，并放在一个连通块中
			ans[b[i].x]=1;
			SCC(b[i].x);
			for(j=1;j<=n;j++)
			{
				if(flag[j]==b[i].x)
					ans[j]=K;//K记录连通块中的个数，对于本题来说等于1的无法传回，大于一的可以传回
			}
		}
		K=1;
	}
	for(i=1;i<=n;i++)
	{
		if(ans[i]==1)
			fout<<'F'<<endl;
		if(ans[i]>1)
			fout<<'T'<<endl;
	}
	return 0;
}