记录编号	388582	评测结果	AAAAAAAAAA
题目名称	[WZOI 2011 S3] 消息传递	最终得分	100
用户昵称	Lunardrop	是否通过	通过
代码语言	C++	运行时间	0.331 s
提交时间	2017-03-29 12:34:42	内存使用	4.20 MiB

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

struct edge
{
	int v, next;
}e[200001];

int u, v, t=0, colnum=0;
int n, m, p=0, cnt=0, dep=0;
int head[100001], dfn[100001], low[100001], sta[100001];
int sum[100001], color[100001];
bool insta[100001];

void add(int x, int y)
{
	e[++cnt].next = head[x];
	e[cnt].v = y;
	head[x] = cnt;
}

void tarjan(int x)
{
	dfn[x] = low[x] = ++dep;
	sta[++p] = x; insta[x]= true;
	for(int i=head[x]; i!=0; i=e[i].next)
	{
		if(dfn[e[i].v]==0)
		{
			tarjan(e[i].v);
			low[x] = min(low[x], low[e[i].v]);
		}
		else if(insta[e[i].v]) low[x] = min(low[x], dfn[e[i].v]);
	}
	
	if(dfn[x]==low[x])
	{
		colnum++;
		do
		{
			color[sta[p]] = colnum;
			sum[colnum]++;
			insta[sta[p]] = false;
		}
		while(sta[p--]!=x);
	}
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("messagez.in", "r", stdin);
//	freopen("messagez.out", "w", stdout);
	freopen("messagew.in", "r", stdin);
	freopen("messagew.out", "w", stdout);
	
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++)
	{
		scanf("%d%d", &u, &v);
		add(u, v);// add(v, u);
	}
	
	for(int i=1; i<=n; i++) if(dfn[i]==0) tarjan(i);
	for(int i=1; i<=n; i++) 
	{
		if(sum[color[i]]>1) printf("T\n");
		else printf("F\n");
	}

	return 0;
}