记录编号	41718	评测结果	AAAAAAAAAA
题目名称	[WZOI 2011 S3] 消息传递	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.511 s
提交时间	2012-08-11 09:04:22	内存使用	2.69 MiB

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN=100100;
int dfn[MAXN],low[MAXN],Index=0;
bool InStack[MAXN];
stack<int> sta; 
vector<int> map[MAXN],res;
int num[MAXN],N,M;

inline void init()
{
	scanf("%d%d\n",&N,&M);
	int u,v; for(int i=1;i<=M;i++)
	{
		scanf("%d%d\n",&u,&v);
		map[u].push_back(v);
	}
}

inline int Min(int a,int b)
{return a<b?a:b;}

void tarjan(int u)
{
	dfn[u]=low[u]=++Index;int v;
	sta.push(u); InStack[u]=1; 
	for(unsigned int i=0;i<map[u].size();i++)
	{
		v=map[u][i];
		if(!dfn[v]) {tarjan(v);low[u]=Min(low[u],low[v]);}
		else if(InStack[v]) low[u]=Min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		int sum=0,tmp;res.clear();
		do
		{
			tmp=sta.top(); sta.pop();
			InStack[tmp]=0;sum++;res.push_back(tmp);
		}while(u!=tmp);
		for(unsigned int i=0;i<res.size();i++)
			num[res[i]]=sum;
	}
}

int main()
{
	freopen("messagew.in","r",stdin);
	freopen("messagew.out","w",stdout);
	init();
	for(int i=1;i<=N;i++)
	{
		if(!dfn[i]) tarjan(i);
		printf("%c\n",num[i]>1?'T':'F');
	}
	return 0;
}