记录编号	221185	评测结果	AAAAAAAAAA
题目名称	[WZOI 2011 S3] 消息传递	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.358 s
提交时间	2016-01-22 10:59:15	内存使用	3.17 MiB

#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
stack<int> s;
const int maxm = 200010,maxn = 100010;
struct node{
	int v;
	int next;
}E[maxm];
int first[maxn],time[maxn],low[maxn],t = 1;
bool instack[maxn];
bool ans[maxn];
void tarjan(int x){
	low[x] = time[x] = t++;
	s.push(x);
	int pt = first[x];
	instack[x]=true;
	while(E[pt].next!=-1){
		if(time[E[pt].v]==0){
			tarjan(E[pt].v);
			if(low[E[pt].v]<low[x])low[x] = low[E[pt].v];
		}
		else{
			if(instack[E[pt].v]&&time[E[pt].v]<low[x])low[x] = time[E[pt].v];
		}
		pt = E[pt].next;
	}
	if(time[x]==low[x]){
		if(s.top()!=x){
			while(s.top()!=x){
				ans[s.top()]=true;
				instack[s.top()]=false;
				s.pop();	
			}
			instack[s.top()]=false;
			s.pop();
			ans[x] = true;
		}
		else {
			instack[x]=false;
			s.pop();
		}
	} 
}
int main()
{
	freopen("messagew.in","r",stdin);
	freopen("messagew.out","w",stdout);
	//tarjan
	memset(time,0,sizeof(time));
	int n,m;
	scanf("%d %d",&n,&m);
	int v1,v2;
	E[0].next = -1;
	for(int i = 1;i<=m;++i){
		scanf("%d %d",&v1,&v2);
		E[i].v = v2;
		E[i].next = first[v1];
		first[v1]=i;
	}//建链表 
	for(int i = 1;i<=n;++i){
		if(!time[i])tarjan(i);
	}
	for(int i = 1;i<=n;++i){
		if(ans[i])printf("T\n");
		else printf("F\n");
	}
	fclose(stdin);fclose(stdout);
	return 0;
}