记录编号	192474	评测结果	AAAAAAAAAA
题目名称	[金陵中学2007] 传话	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2015-10-11 07:56:19	内存使用	0.34 MiB

#include <vector>
#include <algorithm>
#include <stack>
#include <iostream>
#include <fstream>
#define cin fin
#define cout fout

using namespace std;
typedef vector<int> vi;

ifstream fin("messagez.in");
ofstream fout("messagez.out");
const int MAXN(1001), MAXM(10001);
int n, m, dfs_clock, scc_cnt, pre[MAXN], lowlink[MAXN], sccno[MAXN];
vi g[MAXN];
stack<int> s;
inline void find_scc();
void dfs(int);

main()
{
	cin >> n >> m;
	while (m--){
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
	}
	fin.close();
	
	find_scc();
	
	for (int i = 1; i <= n; ++i){
		vi::iterator it;
		for (it = g[i].begin(); it != g[i].end(); ++it)
			if (sccno[i] == sccno[*it]){
				cout << "T\n";
				break;
			}
		if (it == g[i].end())
			cout << "F\n";
	}
	fout.close();
//	for (; ; );
}

inline void find_scc(){
	dfs_clock = scc_cnt = 0;
	for (int i = 1; i <= n; ++i)
		if (! pre[i])
			dfs(i);
}

void dfs(int u)
{
	pre[u] = lowlink[u] = ++dfs_clock;
	s.push(u);
	for (vi::iterator it = g[u].begin(); it != g[u].end(); ++it)
		if (! pre[*it]){
			dfs(*it);
			lowlink[u] = min(lowlink[u], lowlink[*it]);
		}
		else if (! sccno[*it])
			lowlink[u] = min(lowlink[u], pre[*it]);
	if (lowlink[u] == pre[u]){
		++scc_cnt;
		for (; ; ){
			int x = s.top();
			s.pop();
			sccno[x] = scc_cnt;
			if (x == u)
				break;
		}
	}
}