记录编号	539477	评测结果	AAAAAAAAAA
题目名称	[金陵中学2007] 传话	最终得分	100
用户昵称	6666	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2019-08-07 14:39:21	内存使用	13.70 MiB

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=1005;
int n,m;vector<int>v[maxn];
int tim,dfn[maxn],low[maxn],belong[maxn],size[maxn],scc_cnt,cnt,st[maxn];
void Tarjan(int rt){
	dfn[rt]=low[rt]=++tim;
	st[++cnt]=rt;
	for(int i=0;i<v[rt].size();i++){
		int to=v[rt][i];
		if(!dfn[to])//正向边
			Tarjan(to),low[rt]=min(low[rt],low[to]);
		else if(!belong[to])//反向边	
			low[rt]=min(low[rt],dfn[to]);
	}
	if(dfn[rt]==low[rt]){
		scc_cnt++;int k;
		do {
			k=st[cnt--];
			belong[k]=scc_cnt;
			size[scc_cnt]++;
		}while(k!=rt);
	}
}
int main(){
	freopen("messagez.in","r",stdin);freopen("messagez.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int x,y;scanf("%d%d",&x,&y);
		v[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])Tarjan(i);
	for(int i=1;i<=n;i++)
		if(size[belong[i]]>1)puts("T");
		else puts("F");
}