强连通分量Kosaraju

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

using namespace std;

const int maxn=1e5+;

const int maxm=2e5+;

inline int read(){

    int a = ; bool b = ; char x = getchar();

    while(x<''||''<x){

        if(x=='-')b=;

        x=getchar();

    }

    while(''<=x && x<=''){

        a=(a<<)+(a<<)+x-'';

        x=getchar();

    }

    return b ? a : -a ;

}

int n,m;

int first[maxn][],next[maxm][],to[maxm][],end[maxn];

int edge_count[];

inline void add(int x,int y,bool b){

    edge_count[b]++;

    to[ edge_count[b] ][b]=y;

    next[ edge_count[b] ][b]=first[x][b];

    first[x][b]=edge_count[b];

}

int vis[maxn];

int Time=;//时间戳

void dfs_one(int x){

    vis[x]=;

    for(int i=first[x][];i;i=next[i][]){

        if(!vis[ to[i][] ])dfs_one(to[i][]);

    }

    end[++Time]=x;

}

int temp=,cnt[maxn];

void dfs_two(int x){

    vis[x]=temp;

    cnt[temp]++;

    for(int i=first[x][];i;i=next[i][]){

        if(vis[ to[i][] ])continue;

        dfs_two(to[i][]);

    }

}

//0->正向 ，1->反向

int main()

{

    n=read();m=read();

    for(int i=,a,b;i<=m;i++){

        a=read();b=read();

        add(a,b,);add(b,a,);

    }

    for(int i=;i<=n;i++){if(!vis[i])dfs_one(i);}

    memset(vis,,sizeof(vis));

    for(int i=n;i;i--){

        if(vis[ end[i] ])continue;

        temp++;

        dfs_two(end[i]);

    }

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

        if(cnt[ vis[i] ]>)printf("T\n");

        else printf("F\n");

    }

    return ;

}