记录编号	245563	评测结果	AAAAAAAAAA
题目名称	[WZOI 2011 S3] 消息传递	最终得分	100
用户昵称	Riolu	是否通过	通过
代码语言	C++	运行时间	2.017 s
提交时间	2016-04-03 18:09:05	内存使用	6.12 MiB

/*-------------------------------------------------
*  Author:Rainboy
*  time: 2016-03-30 15:42
*  © Copyright 2016 Rainboy. All Rights Reserved.
*-------------------------------------------------*/


/* -----------
 *  原理,:一个分量里的点都可以互相访问
 * 算法实现:
 *      1.初始化 dfn[i], low[i]
 *      2.对i所有相临的结点j
 *          1.if !vis[j] dfs[j]
 *          2.if vis[j] low[i] =dfn[j]
 *      3.if dfn[i] = low[i]
 * */


#include <cstdio>
#include <cstring>
#include<iostream>
#define maxn 200001 //最多的点
using namespace std;
bool instack[maxn] ={0}; // =false
int low[maxn];
int dfn[maxn] ={0};
int color[maxn]; // color[i] 点i的强连通分量
int stack[maxn],top; // 自己维护的stack ,可以用 STL stack
int cnt =0,indexk=0;
char ans[maxn];
//存图
int first[maxn];
int u[maxn],v[maxn],next[maxn];

void tarjan(int x){
    int j;
    dfn[x] = low[x] = ++indexk;
    instack[x] =true;
    stack[++top] = x;
    int e = first[x];
    for(; e != -1; e = next[e]){
        j = v[e];
        if( !dfn[j] ) // dnf[j] !=0 表示 这个点没有被访问过
        {
            tarjan(j);
            if(low[j] < low[x])
                low[x] = low[j];
        } 
        else if(instack[j] && dfn[j] < low[x])
            low[x] = dfn[j];
    }
	if(dfn[x] == low[x])
        {
            cnt++;int kk=0;
            do{
				kk++;
                j=stack[top--];
				ans[j]='T';
                instack[j] = false;
                color[j] = cnt;
            }
            while(j !=x);
			if(kk==1) ans[x]='F';
        }
}

int main(){
	freopen("messagew.in","r",stdin);
	freopen("messagew.out","w",stdout);
    top = 0;
    int i,j,k,n;
	int T;
    memset(first,-1,sizeof(first));
    scanf("%d%d",&T,&n);
    //读取图 这里用边集数组
    i=1;
	for(i=1;i<=n;i++){
		scanf("%d%d",&u[i],&v[i]);
        next[i] = first[u[i]];
        first[u[i]] = i;
    }
    for(i=1;i<=T;i++){ // 遍历所有点
        if(!dfn[i]) // 没有被访问过
            tarjan(i);
    }

	//cout<<cnt<<endl;

	/*for(k=1;k<=T;k++)
	{
		int t=color[k],ok=0;
			for(j=1;j<=T;j++)
				if(color[j]==t&&j!=k){
					cout<<"T"<<endl;ok=1;
					break;
					}
		if(ok==0) cout<<"F"<<endl;		
		}*/
	for(k=1;k<=T;k++)
		cout<<ans[k]<<endl;
    return 0;
}