记录编号	397904	评测结果	AAAAAAAAAA
题目名称	[金陵中学2007] 传话	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2017-04-21 09:41:22	内存使用	0.34 MiB

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

const int MAXN = 1e3 + 10;

inline int in(void){
	char tmp = getchar();
	int res = 0;
	while(!isdigit(tmp))tmp = getchar();
	while(isdigit(tmp))
		res = (res + (res << 2) << 1) + (tmp ^ 48),
		tmp = getchar();
	return res;
}

struct EDGE{
	int fr, to, ne;
	
	EDGE(){;}
	EDGE(int _fr, int _to, int _ne){
		fr = _fr, to = _to, ne = _ne;
	}
};

inline void add_edge(int fr, int to);
void dfs(int u);
int Find(int a);
inline void Union(int a, int b);

vector<EDGE> edge;
int head[MAXN];
int dfn[MAXN], low[MAXN];
int stack[MAXN], top;
int fa[MAXN];
bool ins[MAXN];
bool ans[MAXN];
int N, M;

int main(){
#ifndef LOCAL
	freopen("messagez.in", "r", stdin);
	freopen("messagez.out", "w", stdout);
#else
	freopen("test.in", "r", stdin);
#endif
	memset(head, 0xff, sizeof(head));
	
	N = in(), M = in();
	for(int i = 1; i <= N; ++i)fa[i] = i;
	for(int i = 1, a, b; i <= M; ++i){
		a = in(), b = in();
		add_edge(a, b);
	}
	for(int i = 1; i <= N; ++i)if(!dfn[i])dfs(i);
	
	for(int i = 1, a; i <= N; ++i){
		if((a = Find(i)) != i){
			ans[a] = true;
			ans[i] = true;
		}
	}
	
	for(int i = 1; i <= N; ++i){
		if(ans[i])printf("T\n");
		  else printf("F\n");
	}
	
	return 0;
}

inline void add_edge(int fr, int to){
	edge.push_back(EDGE(fr, to, head[fr])), head[fr] = edge.size() - 1;
	return ;
}

void dfs(int u){
	static int cnt = 0;
	int v;
	low[u] = dfn[u] = ++cnt;
	stack[top++] = u;
	ins[u] = true;
	for(int i = head[u]; ~i; i = edge[i].ne){
		v = edge[i].to;
		if(!dfn[v]){
			dfs(v);
			low[u] = min(low[u], low[v]);
		}
		else if(ins[v]){
			low[u] = min(low[u], dfn[v]);
		}
	}
	
	if(low[u] == dfn[u]){
		do{
			--top;
			Union(u, stack[top]);
			ins[stack[top]] = false;
		}while(u != stack[top]);
	}
	return ;
}

int Find(int a){
	if(a == fa[a])return a;
	return fa[a] = Find(fa[a]);
}

inline void Union(int a, int b){
	static int cnt = 0;
	fa[Find(a)] = Find(b);
	++cnt;
	return ;
}