记录编号	438162	评测结果	AAAAAAAAAA
题目名称	[WZOI 2011 S3] 消息传递	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.237 s
提交时间	2017-08-15 16:02:56	内存使用	3.46 MiB

# include <bits/stdc++.h>
# define MAXN 100023
using namespace std;

inline int gn() {
    int k = 0, f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) k = k * 10 + c - '0';
    return k * f;
}

vector<int> to[MAXN];
int n, m, ans_cnt = 1, dfn[MAXN], bel[MAXN], tms[MAXN];

void dfs(int u) {
    static int stack[MAXN], top, low[MAXN], cnt;
    static bool ins[MAXN];
    dfn[u] = low[u] = ++cnt;
    stack[top++] = u;
    ins[u] = 1;
    int siz = (int) to[u].size();
    for(int i = 0, v; i < siz; i++) {
        v = to[u][i];
        if (!dfn[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (ins[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]) {
        do {
            bel[stack[--top]] = ans_cnt;
            tms[ans_cnt]++;
            ins[stack[top]] = 0;
        } while (stack[top] ^ u);
        ++ans_cnt;
    }
}

inline bool cmp(const vector<int> &a, const vector<int> &b) {
    if (a.size() ^ b.size()) return a.size() > b.size();
    for (unsigned int i = 0; i < a.size(); ++i)
        if (a[i] ^ b[i]) return a[i] < b[i];
    return false;
}

int main() {
    freopen("messagew.in", "r", stdin);
    freopen("messagew.out", "w", stdout);
    n = gn(), m = gn();
    for (int i = 1; i <= m; i++) {
        int f = gn(), t = gn();
        to[f].push_back(t);
    }
    for (int i = 1; i <= n; i++) if(!bel[i]) dfs(i);
    for (int i = 1; i <= n; i++) {
        if(tms[bel[i]] > 1) puts("T");
        else puts("F");
    }
}