记录编号	172278	评测结果	AAAAAAAAAA
题目名称	[WZOI 2011 S3] 消息传递	最终得分	100
用户昵称	旧梦	是否通过	通过
代码语言	C++	运行时间	0.904 s
提交时间	2015-07-24 11:31:43	内存使用	14.42 MiB

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
bool vis[2000000];
int num[1000000];
int countt[1000000];
int cnt=0,n,m;
vector<int>v[200000];
vector<int>ni[200000];
vector<int>s;

void dfs(int x){
	vis[x]=1;
	for (int i=0;i<v[x].size();++i)
		if (!vis[v[x][i]])
		   dfs(v[x][i]);
	s.push_back(x);
}

void dfs2(int x){
	num[x]=cnt;
	countt[cnt]+=1;
	vis[x]=1;
	for (int i=0;i<ni[x].size();++i)
	   if (!vis[ni[x][i]])
		  dfs2(ni[x][i]);
}

int main()
{
	freopen("messagew.in","r",stdin);
	freopen("messagew.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		ni[y].push_back(x);
	}
	for (int i=1;i<=n;++i)
	   if (!vis[i])
		  dfs(i);
	for (int i=1;i<=n;++i) vis[i]=0;
	for (int i=s.size()-1;i>=0;--i)
	   if (!vis[s[i]]){
			cnt++;
            dfs2(s[i]);
	   }
	for (int i=1;i<=n;++i)
	   if (countt[num[i]]>1) printf("T\n");
		  else printf("F\n");
	return 0;
}