记录编号	348801	评测结果	AAAAAAAAAA
题目名称	[WZOI 2011 S3] 消息传递	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	0.427 s
提交时间	2016-11-14 16:40:31	内存使用	4.06 MiB

#include <stack>
#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXN=100010;
const int MAXM=200010;
struct PATH{
	int to,next,dis;
	PATH(){to=next=-1;}
};
struct PIC{
	int head[MAXN];
	int pre[MAXN];
	int lowlink[MAXN];
	int sccno[MAXN];
	int scc_size[MAXN];
	PATH table[MAXM];
	PIC(){memset(head,-1,sizeof(head));}
	void add(int from,int to){
		static int lens=0;
		table[++lens].next=head[from];
		table[lens].to=to;
		head[from]=lens;
	}
	void Tarjan(int from){
		static int lock=0;
		static int scc_cnt=0;
		static std::stack<int> s;
		pre[from]=lowlink[from]=++lock;
		s.push(from);
	#define to table[i].to
		for(int i=head[from];i!=-1;i=table[i].next)
			if(!pre[to]){Tarjan(to);lowlink[from]=std::min(lowlink[from],lowlink[to]);}
			else if(!sccno[to]){lowlink[from]=std::min(lowlink[from],pre[to]);}
		if(lowlink[from]==pre[from]){
			++scc_cnt;
			while(!s.empty()){
				int x=s.top();s.pop();
				sccno[x]=scc_cnt;
				++scc_size[scc_cnt];
				if(x==from)break;
			}
		}
	#undef to
	}
	void sccfind(int N){
		for(int i=1;i<=N;++i)
			if(!pre[i])Tarjan(i);
			
	}
	bool check(int i){
		return scc_size[sccno[i]]!=1;
	}
}pic;
int main(){
	freopen("messagew.in","r",stdin);
	freopen("messagew.out","w",stdout);
	int N,M,a,b;
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;++i){
		scanf("%d%d",&a,&b);
		pic.add(a,b);
	}pic.sccfind(N);
	for(int i=1;i<=N;++i){
		printf(pic.check(i)?"T\n":"F\n");
	}while(getchar()!=EOF);
	return 0;
}