◦思想：

◦

◦做一遍DFS，用dfn[i]表示编号为i的节点在DFS过程中的访问序号(也可以叫做开始时间）用low[i]表示i节点DFS过程中i的下方节点所能到达的开始时间最早的节点的开始时间。（也就是之后的深搜所能到达的最小开始时间）初始时dfn[i]=low[i]

◦

◦在DFS过程中会形成一搜索树。在搜索树上越先遍历到的节点，显然dfn的值就越小。

◦

◦DFS过程中，碰到哪个节点，就将哪个节点入栈。栈中节点只有在其所属的强连通分量已经全部求出时，才会出栈。

◦（对于一个强连通分量和一个指出去的有向边，在输出这个强连通分量的时候，那条指出去的边的终点已经作为一个强连通分量统计，并且出栈了。）

◦如果发现某节点u有边连到搜索树（栈）中栈里的节点v，则更新u的low 值为dfn[v](更新为low[v]也可以，更新为low可以算是压缩路径，速度略快）。

#include<iostream>

using namespace std;

#include<cstdio>

#define N 100100

#include<vector>

vector<int>G[N];

vector<int>ans[N];

int clac=;

bool inzhan[N];

#include<stack>

#include<cstring>

stack<int>s;

int low[N],dfn[N];

bool flag[N]={},ok[N]={};

int n,m;

int Index;

void input()

{

    Index=;

    scanf("%d%d",&n,&m);

    int a,b;

    for(int i=;i<=m;++i)

    {

        scanf("%d%d",&a,&b);

        G[a].push_back(b);

    }

    memset(inzhan,false,sizeof(inzhan));

    memset(dfn,-,sizeof(dfn));

    memset(low,-,sizeof(low));

}

void Tarjan(int k)

{

    int  j;

    dfn[k]=low[k]=++Index;/*tarjan过程，记录到达该点的时间，和从该点出发能到达的时间最小的点*/

    inzhan[k]=true;/*入栈*/

    s.push(k);

    for(int i=;i<G[k].size();++i)

    {

        int tp=G[k][i];/*邻接表储存，G[k][i]表示从k点出发的第i条边的终点编号*/

        if(low[tp]==-)

        {

            Tarjan(tp);

            low[k]=min(low[k],low[tp]);

        }

        else if(inzhan[tp])

        low[k]=min(low[tp],low[k]);

        /*整理总共有三种情况：未被访问，访问了但是是不是强连通分量还不知道（也就是仍在栈中），访问了已经出栈了（这种不用处理，因为如果这个点在好几个强连通分量中，那么他此时一定没有出栈。因为深搜嘛）*/

    }

    if(low[k]==dfn[k])/*low[k]==dfn[k]是这个强连通分量的标志，也就是起始位置，不能再向上找了*/

    {

        int l;

        clac++;/*强连通分量个数*/

        do{

        l=s.top();

        s.pop();

        ans[clac].push_back(l);

        inzhan[l]=false;

        }while(l!=k);

       if(ans[clac].size()>)

       flag[clac]=true;/*记录这个强连通分量中的所有点是可以传话成功的，下面在重标记每一个点*/

    }

}

void OUT()

{

    for(int i=;i<=clac;++i)

    if(flag[i])

    {

        for(int j=;j<ans[i].size();++j)

        ok[ans[i][j]]=true;

    }

    for(int i=;i<=n;++i)

    if(ok[i])

    printf("T\n");

    else printf("F\n");

}

int main()

{

    freopen("messagew.in","r",stdin);

    freopen("messagew.out","w",stdout);

    input();

    for(int i=;i<=n;++i)

    if(dfn[i]==-)

    Tarjan(i);

    OUT();

    fclose(stdin);

    fclose(stdout);

    return ;

}