记录编号	306242	评测结果	AAAAAAAAAA
题目名称	619.[金陵中学2007] 传话	最终得分	100
用户昵称	Tiny	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2016-09-11 19:27:48	内存使用	3.26 MiB

#include <stdio.h>
#include <string.h>

template <typename T> inline void Read(T &num) {
	num = 0; char ch; short minus = 1;
	while (ch = getchar(), ch < '-' || ch > '9');
	if (ch == '-') ch = getchar(), minus = -1;
	while (num = num * 10 + ch - '0', ch = getchar(), ch >= '0' && ch <= '9');
	num *= minus;
}

const size_t maxn = 100000 + 10, maxm = 200000 + 10;

class Graph {
	int Stack[maxn], top;
	bool instack[maxn];
	
	inline void SCC_Tarjan(int u) {
		dfn[u] = low[u] = ++dfs_time;
		Stack[++top] = u; instack[u] = true;
		int v;
		for (int i = pre[u]; i; i = E[i].next) {
			v = E[i].to;
			if (!dfn[v]) {
				SCC_Tarjan(v);
				if (low[u] > low[v]) low[u] = low[v];
			}
			else if (instack[v] && low[u] > dfn[v]) low[u] = dfn[v];
		}
		if (dfn[u] == low[u]) {
			++cnt;
			do {
				v = Stack[top--];
				instack[v] = false;
				scc[v] = cnt;
			} while (v != u);
		}
	}
	
public:
	int n, m;
	struct Edge { int to, next; } E[maxm];
	int pre[maxn], tot;
	int dfn[maxn], low[maxn], dfs_time;
	int scc[maxn], cnt;
	
	inline Graph() {
		tot = cnt = dfs_time = top = 0;
		memset(pre, 0, sizeof(pre));
		memset(dfn, 0, sizeof(dfn));
		memset(low, 0, sizeof(low));
		memset(Stack, 0, sizeof(Stack));
		memset(scc, 0, sizeof(scc));
	}
	
	inline void Insert(const int &u, const int &v) {
		E[++tot].to = v; E[tot].next = pre[u]; pre[u] = tot;
	}
	
	inline void get_SCC() {
		for (int i = 1; i <= n; ++i) if (!dfn[i]) SCC_Tarjan(i);
	}
};

int done[maxn] = {0};

#define SUBMIT

int main() {
#ifdef SUBMIT
	freopen("messagez.in", "r", stdin);
	freopen("messagez.out", "w", stdout);
#endif

	Graph G;
	scanf("%d%d", &G.n, &G.m);
	int u, v;
	for (int i = 1; i <= G.m; ++i) {
		scanf("%d%d", &u, &v);
		G.Insert(u, v);
	}
	G.get_SCC();
	for (int i = 1; i <= G.n; ++done[G.scc[i++]]) ;
	for (int i = 1; i <= G.n; ++i) {
		if (done[G.scc[i]] == 1) puts("F");
		else if (done[G.scc[i]] > 1) puts("T");
	}

#ifndef SUBMIT
	puts("\n--------------------");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif	
	return 0;
}