记录编号	546673	评测结果	AAAAAAAAAA
题目名称	[WZOI 2011 S3] 消息传递	最终得分	100
用户昵称	云卷云书	是否通过	通过
代码语言	C++	运行时间	1.649 s
提交时间	2019-11-11 21:52:02	内存使用	19.76 MiB

#include<bits/stdc++.h>
using namespace std;
const int maxn=100007;
int n,m,dfn[maxn],low[maxn],num,ins[maxn],cnt,c[maxn];
vector<int> e[maxn],scc[maxn];
stack<int> s;
void add(int x,int y){
	e[x].push_back(y);
}
void tarjan(int x){
	dfn[x]=low[x]=++num;
	s.push(x),ins[x]=1;
	for(int i=0;i<e[x].size();i++){
		int v=e[x][i];
		if(!dfn[v]){
			tarjan(v);
			low[x]=min(low[x],low[v]);
		}
		else if(ins[v])
		low[x]=min(low[x],dfn[v]);
	    }
		if(dfn[x]==low[x]){
			cnt++;
			int y=-1;
			while(y!=x){
			     y=s.top();
			     c[y]=cnt;
			     s.pop();
			     scc[cnt].push_back(y);
			     ins[y]=0;
		    }
		}
	return;
}
int main(){
    freopen("messagew.in","r",stdin);
	freopen("messagew.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	for(int i=1;i<=n;i++){
	if(!dfn[i]) tarjan(i);
    }
	for(int i=1;i<=n;i++){
		int q=c[i];
		if(scc[q].size()>1)
		cout<<'T'<<endl;
		else
		cout<<'F'<<endl;
	}
	return 0;
}