首页 > 代码库 > POJ 3180-The Cow Prom (图论-有向图强联通tarjan算法)

POJ 3180-The Cow Prom (图论-有向图强联通tarjan算法)

题目大意:有n个牛在一块, m条单项绳子, 有m个链接关系, 问有多少个团体内部任意两头牛可以相互可达

解题思路:有向图强连通分量模版图

代码如下:

技术分享
#include<stdio.h>#include<vector>#include<map>#include<set>#include<algorithm>using namespace std;typedef long long ll;const int N = 10003;vector<int>G[N], DQ;int low[N], dfn[N], tot;bool mk[N];int n, m, ans;void init(){    ans = tot = 0;    DQ.clear();    for(int i=1; i<=n; ++ i)    {        G[i].clear();        low[i] = dfn[i] = -1;        mk[i] = false;    }}void tarjan(int u, int f){    dfn[u] = low[u] = ++ tot;    DQ.push_back(u);    mk[u] = true;    for(int i = 0; i<G[u].size(); ++ i)    {        int v = G[u][i];        if(dfn[v] == -1)        {            tarjan(v, u);            low[u] = min(low[u], low[v]);        }        else if(mk[v])            low[u] = min(low[u], dfn[v]);    }    if(dfn[u] == low[u])    {        int s;        int k = 0;        do        {            s = DQ.back();            k ++;            DQ.pop_back();            mk[s] = false;        }        while(u != s);        if(k > 1)            ans ++;    }}void solve(){    for(int i=1; i<=n; ++ i)    {        if(dfn[i] == -1)            tarjan(i, -1);    }    printf("%d\n", ans);}int main(){    while(~scanf("%d%d", &n, &m))    {        init();        for(int i=1; i<=m; ++ i)        {            int u, v;            scanf("%d%d", &u, &v);            G[u].push_back(v);        }        solve();    }    return 0;}
View Code

 

POJ 3180-The Cow Prom (图论-有向图强联通tarjan算法)