记录编号	433868	评测结果	AAAAAAAAAA
题目名称	[WZOI 2011 S3] 消息传递	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.316 s
提交时间	2017-08-06 14:50:48	内存使用	3.36 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int maxn=100010;
const int maxm=200010;
int n,m;
int dfn[maxn],low[maxn],tim,cnt,belong[maxn],inzhan[maxn];
stack<int>zhan;
vector<int>g[maxn];
int fa[maxn];
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void tarjan(int u){
	dfn[u]=low[u]=++tim;
	zhan.push(u);inzhan[u]=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(inzhan[v]&&dfn[v]<low[u])low[u]=dfn[v];
	} 
	if(dfn[u]==low[u]){
		cnt++;int v;
		do{
			v=zhan.top();
			zhan.pop();
			inzhan[v]=0;
			belong[v]=cnt;
			//fa[find(v)]=cnt;
		}
		while(u!=v);
	}
}
int main(){
	freopen("messagew.in","r",stdin);
	freopen("messagew.out","w",stdout);
	n=read();m=read();
	//cnt=n;
	//for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		g[u].push_back(v); 
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])tarjan(i);
	}
	for(int i=1;i<=n;i++){
		int ok=belong[i];
		int flag=0;
		for(int j=0;j<g[i].size();j++){
			if(belong[g[i][j]]==ok){puts("T");flag=1;break;}
		}
		if(flag==0)puts("F");
	}
	return 0;
}