记录编号	41692	评测结果	AAAAAAAAAA
题目名称	[WZOI 2011 S3] 消息传递	最终得分	100
用户昵称	Czb。	是否通过	通过
代码语言	C++	运行时间	0.504 s
提交时间	2012-08-09 15:16:50	内存使用	3.11 MiB

#include<stdio.h>
#include<vector>
#include<stack>

using namespace std;

int n,m,Index,count;

int dfn[100001],low[100001];

bool flag[100001];

vector <int> v[100001],u[100001];

stack <int> s;

void dfs(int x)
{
	int i,y;
	dfn[x]=low[x]=++Index;
	flag[x]=true;
	s.push(x);
	for(i=0;i<v[x].size();i++)
	{
		y=v[x][i];
		if(!dfn[y])
		{
			dfs(y);
			if(low[y]<low[x])
				low[x]=low[y];
		}
		else if(flag[y]&&dfn[y]<low[x])
			low[x]=dfn[y];
	}
	if(low[x]==dfn[x])
	{
		count++;
		do
		{
			y=s.top();
			s.pop();
			flag[y]=false;
			u[count].push_back(y);
		}
		while(x!=y);
	}
}

int main()
{
	freopen("messagew.in","r",stdin);
	freopen("messagew.out","w",stdout);
	int i,x,y;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
	}
	for(i=1;i<=n;i++)
	if(!dfn[i])dfs(i);
	for(i=1;i<=count;i++)
	{
		if(u[i].size()==1)
			flag[u[i][0]]=true;
	}
	for(i=1;i<=n;i++)
	{
		if(flag[i])
			printf("F\n");
		else
			printf("T\n");
	}
	return 0;
}