记录编号	261979	评测结果	AAAAAAAAAA
题目名称	[WZOI 2011 S3] 消息传递	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.329 s
提交时间	2016-05-19 11:28:48	内存使用	3.45 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
inline void read(int &x){
	x=0;char ch;
	while(ch=getchar(),ch<'!');
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');
}
const int maxn = 100000 + 10 ;
const int maxm = 200000 + 10 ;
struct Edge{
    int to,next;	
}G[maxm];
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
int vis[maxn],times,dfn[maxn],low[maxn],n,m;
int st[maxn],top;
int head[maxn],cnt;
void add(int u,int v){
	G[++cnt].to=v;
	G[cnt].next=head[u];
	head[u]=cnt;
}
bool is[maxn];
stack<int> s;
void tarjan(int x){
	low[x] = dfn[x] = ++times;
	s.push(x);vis[x]=true;
	for(int i=head[x];i;i=G[i].next){
		int v = G[i].to;
		if(!dfn[v]){
			tarjan(v);
			low[x] = cat_min(low[x],low[v]);
		}else if(vis[v]) 
			low[x] = cat_min(dfn[v],low[x]);
	}
	if(dfn[x]==low[x]){
		if(s.top()!=x){
			while(s.top()!=x){
				is[s.top()]=true;
				vis[s.top()]=false;
				s.pop();	
			}
			vis[s.top()]=false;
			s.pop();
			is[x] = true;
		}else{
			vis[x]=false;
			s.pop();
		}
	} 
}
int main(){
	freopen("messagew.in","r",stdin);
	freopen("messagew.out","w",stdout);
	read(n),read(m);
    int u,v;
    while(m--){
    	read(u),read(v);
    	add(u,v);
	}
	for(int i=1;i<=n;++i)
		if(!dfn[i])
	 		tarjan(i);
	for(int i=1;i<=n;i++){
		if( is[i] ) printf("T\n");
		else printf("F\n");
	}
}