记录编号	172505	评测结果	AAAAAAAAAA
题目名称	[WZOI 2011 S3] 消息传递	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.496 s
提交时间	2015-07-25 11:12:42	内存使用	5.34 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
struct dd
{
	int kaishi;
    int zhong;
    int next;
}jie[202000];

int Min(int h,int y)
{
	if(h>y) return y;
	return h;
}
int v[100150],times,dfn[100250],low[100250],n,x,m,y;

int st[100250],ans1,ans2,tot,num,gh[110050],numk[100250];

int head[100125],top;

void add(int x,int y)
{
	tot++;
	jie[tot].kaishi=x;
	jie[tot].zhong=y;
	jie[tot].next=head[x];
	head[x]=tot;
}
void tar(int y)
{
	times++;
	dfn[y]=low[y]=times;
	st[++top]=y,v[y]=1;
	for(int i=head[y];i!=-1;i=jie[i].next)
	{
		int yu=jie[i].zhong;
		if(!dfn[yu])
		{
			tar(yu);
			low[y]=Min(low[y],low[yu]);
		}
		else
		 if(v[yu])
		 {
		 	low[y]=Min(low[y],dfn[yu]);
		 }
	}
	if(low[y]==dfn[y])
	{
		++num;
		int yulin;
		do{
			yulin=st[top--];
			v[yulin]=0;
			gh[yulin]=num;
			numk[num]++;
		}while(yulin!=y);
	}
}
void work()
{
	for(int i=1;i<=n;++i)
	  if(numk[gh[i]]>1)
	   printf("T\n");
	  else
	   printf("F\n");
	
}
int main()
{   
    freopen("messagew.in","r",stdin);
	freopen("messagew.out","w",stdout);
    memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
      scanf("%d%d",&x,&y),add(x,y);
	for(int i=1;i<=n;++i)
	 if(!dfn[i])
	  tar(i);
	work();
	//while(1);
}