记录编号	250362	评测结果	AAAAAAAAAA
题目名称	1001.[WZOI 2011 S3] 消息传递	最终得分	100
用户昵称	Marvolo	是否通过	通过
代码语言	C++	运行时间	0.641 s
提交时间	2016-04-14 21:36:00	内存使用	27.40 MiB

#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;

long long i,n,m,a,b,zh,dp,d;
long long bh[1000010],s[1000010],bj[1000010];
long long f[100010],v[100010];
long long dfn[100010],low[100010];

vector<long long> l[100010];

long long min(long long a,long long b){return (a<b)?a:b;}

void print(long long q){
	zh++;
	bh[zh]++;
	bj[q]=zh;
	while (s[dp]!=q) {
		bh[zh]++;
		f[s[dp]]=0;
		bj[s[dp]]=zh;
		dp--;
	}
	f[s[dp]]=0;
	dp--;
	return;
}

void dfs(long long x){
	long long i;
	d++;
	dfn[x]=low[x]=d;
	dp++;
	s[dp]=x;
	f[x]=1;
	
	/*cout<<"-------"<<endl;
	writeln(d);
	writeln(dp);
	writeln(x);
	cout<<"-------"<<endl;*/
	
	if (l[x].size()!=0) for (i=0;i<=l[x].size()-1;i++)
	{
	//	cout<<"'''"<<endl;
	//	writeln(l[x][i]);
	//	cout<<"'''"<<endl;
		if (v[l[x][i]]==0) {
			v[l[x][i]]=1;
			dfs(l[x][i]);
			low[x]=min(low[x],low[l[x][i]]);
		} else
		if (f[l[x][i]]==1) low[x]=min(low[x],dfn[l[x][i]]);
	}
	if (low[x]==dfn[x]) print(x);
	return;
}

int main(){
	freopen("messagew.in","r",stdin);
	freopen("messagew.out","w",stdout);
	scanf("%d%d",&n,&m);

	for (i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		if (a==b) continue;
		l[a].push_back(b);	
	}
	
	for (i=1;i<=n;i++)
	{
		if (v[i]==0) {
			v[i]=1;
			dfs(i);
		}
	}
	for (i=1;i<=n;i++)
	if (bh[bj[i]]>1) printf("T\n"); else printf("F\n");
	return 0;
}