首页 > 代码库 > POJ 2186 Popular Cows --强连通分量

POJ 2186 Popular Cows --强连通分量

2024-07-11 14:27:25   220人阅读

题意：给定一个有向图，问有多少个点由任意顶点出发都能达到。

分析：首先，在一个有向无环图中，能被所有点达到点，出度一定是0。

先求出所有的强连通分支，然后把每个强连通分支收缩成一个点，重新建图，这样，这个有向图就变成了一个有向无环图。

在这个新的图中，只需知道出度为0的点有几个即可。

如果出度为0的点超过1个，则输出0；否则输出出度为0的点所代表的那个强连通分支的分量数即可。

用Tarjan求强连通分量

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>#include <string>#include <vector>#include <stack>using namespace std;#define N 10007vector<int> G[N],G2[N];stack<int> stk;int instk[N],cnt,Time,n,m,out[N];int low[N],dfn[N],bel[N],num[N];void tarjan(int u){    low[u] = dfn[u] = ++Time;    stk.push(u);    instk[u] = 1;    for(int i=0;i<G[u].size();i++)    {        int v = G[u][i];        if(!dfn[v])        {            tarjan(v);            low[u] = min(low[u],low[v]);        }        else if(instk[v])            low[u] = min(low[u],dfn[v]);    }    if(low[u] == dfn[u])    {        cnt++;        int v;        do        {            v = stk.top();            stk.pop();            instk[v] = 0;            bel[v] = cnt;            num[cnt]++;        }while(u != v);    }}void Tarjan(){    memset(bel,0,sizeof(bel));    memset(low,0,sizeof(low));    memset(dfn,0,sizeof(dfn));    memset(instk,0,sizeof(instk));    memset(num,0,sizeof(num));    memset(out,0,sizeof(out));    while(!stk.empty())        stk.pop();    Time = cnt = 0;    for(int i=1;i<=n;i++)        if(!dfn[i])            tarjan(i);}void Build(){    int i,j;    for(i=0;i<=cnt;i++)        G2[i].clear();    for(i=1;i<=n;i++)    {        for(j=0;j<G[i].size();j++)        {            int v = G[i][j];            if(bel[i] != bel[v])            {                G2[bel[i]].push_back(bel[v]);                out[bel[i]]++;            }        }    }}int main(){    int i,j,u,v;    while(scanf("%d%d",&n,&m)!=EOF)    {        for(i=0;i<=n;i++)            G[i].clear();        for(i=0;i<m;i++)        {            scanf("%d%d",&u,&v);            G[u].push_back(v);        }        Tarjan();        Build();        int ans = 0;        int flag = 0;        int tag = 1;        for(i=1;i<=cnt;i++)        {            if(out[i])                continue;            if(flag)            {                tag = 0;                break;            }            else            {                ans += num[i];                flag = 1;            }        }        if(!tag)            puts("0");        else            printf("%d\n",ans);    }    return 0;}
View Code

 


联系
我们