POJ(2186)强连通分量分解

#include<cstdio>

#include<vector>

#include<cstring>

using namespace std;

const int MAX_N=;

vector<int> G[MAX_N];

vector<int> rG[MAX_N];//存储边反向之后的图

vector<int> PostOrder;//存储图的后序遍历

int V,E;

bool used[MAX_N];

int comp[MAX_N];//存储每个结点所属的连通分量

void addEdge(int u,int v)

{

    G[u].push_back(v);

    rG[v].push_back(u);

}

void dfs(int u)

{

    used[u]=true;

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

    {

        int v=G[u][i];

        if(!used[v])

            dfs(v);

    }

    PostOrder.push_back(u);

}

void rdfs(int u,int k)

{

    used[u]=true;

    comp[u]=k;

    for(int i=;i<rG[u].size();i++)

    {

        int v=rG[u][i];

        if(!used[v])

            rdfs(v,k);

    }

}

int scc()

{

    memset(used,false,sizeof(used));

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

    {

        if(!used[i])

            dfs(i);

    }

    memset(used,false,sizeof(used));

    int k=;

    for(int i=PostOrder.size()-;i>=;i--)

    {

        int v=PostOrder[i];

        if(!used[v])

            rdfs(v,k++);

    }

    return k;

}

int main()

{

    scanf("%d %d",&V,&E);

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

    {

        int u,v;

        scanf("%d %d",&u,&v);

        addEdge(u,v);

    }

    int n=scc();

    int u=,num=;

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

    {

        if(comp[i]==n-)//可能的答案必为最后一个强连通分量

        {

            u=i;

            num++;

        }

    }

    memset(used,false,sizeof(used));

    rdfs(u,);//若最后一个连通分量的中的一点,能按反向边将所有结点遍历则该联通分量为答案

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

    {

        if(!used[i])

        {

            num=;

            break;

        }

    }

    printf("%d\n",num);

    return ;

}