记录编号	74857	评测结果	AAAAAAAAAA
题目名称	[WZOI 2011 S3] 消息传递	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	2.041 s
提交时间	2013-10-26 16:24:06	内存使用	4.98 MiB

#include<fstream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
ifstream fin("messagew.in");
ofstream fout("messagew.out");
int f[100001],shijian=0,color[100001],K=1;
int ANS[100001];//存节点所处的连通块的标号
int CN[100001];//某个连通块所拥有的节点数
bool flag[100001]={0};
int counter=0;
vector<int> adj[100001];
vector<int> New[100001];
int N,M;
class woca
{
public:
	int x;
	int y;
}R[100001];
void dfs(int x)
{
	color[x]=1;++shijian;
	for(int i=0;i<adj[x].size();i++)
	{
		if(color[adj[x][i]]==0)
			dfs(adj[x][i]);
	}
	color[x]=2;f[x]=++shijian;
}
bool compare(woca n,woca m)
{
	if(n.y>m.y)
		return 1;
	else
		return 0;
}
void SCC(int x)
{
	flag[x]=1;
	ANS[x]=counter;
	for(int i=0;i<New[x].size();i++)
	{
		if(flag[New[x][i]]==0)
		{
			K++;//先跑一号连通块
			SCC(New[x][i]);
		}
	}
}
int main()
{
	fin>>N>>M;
	int i,A,B;
	for(i=1;i<=M;i++)
	{
		fin>>A>>B;
		adj[A].push_back(B);
		New[B].push_back(A);
	}
	for(i=1;i<=N;i++)
	{
		if(color[i]==0)
			dfs(i);
	}
	for(i=1;i<=N;i++)
	{	R[i].x=i;R[i].y=f[i];}
	sort(R+1,R+N+1,compare);
	for(i=1;i<=N;i++)
	{
		if(CN[ANS[R[i].x]]==0)
		{
			counter++;
			SCC(R[i].x);
			CN[counter]=K;
		}
		K=1;
	}
	for(i=1;i<=N;i++)
	{
		if(CN[ANS[i]]==1)
			fout<<'F'<<endl;
		else
			fout<<'T'<<endl;
	}
	return 0;
}