The Cow Prom – POJ 3180 – TARJAN 强连通 – 模板

题目链接

https://cn.vjudge.net/problem/POJ-3180

题目大意

给出一个有向图,求含有元素大于1的强连通分量的个数。

解题思路

tarjan模板题。有关tarjan的讲解详见https://www.cnblogs.com/liwenchi/p/7259306.html

tarjan其他用法

tarjan还被用作求割点,写法与求强连通略有不同,详见https://jhcloud.top/blog/?p=1567

代码

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int maxn=5e5+10;
vector<int>mp[maxn];
int dfn[maxn],low[maxn],vis[maxn];
int cnt,ans;

stack<int>s;

void tarjan(int u)
{
    s.push(u);
    vis[u]=true;
    low[u]=dfn[u]=++cnt;
    int len=mp[u].size();
    for(int i=0;i<len;i++)
    {
        int v=mp[u][i];
        if(!dfn[v])//若未遍历过
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v])//若遍历过
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u])//强连通根,将其外面的元素都出栈
    {
        int num=0;//此强连通分量中元素的个数
        int now=u;
        while(1)
        {
            num++;
            vis[s.top()]=0;
            if(s.top()==now)
            {
                s.pop();
                break;
            }
            s.pop();
        }
        if(num>1)
            ans++;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int n,m,u,v;
    cnt=0;
    ans=0;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        mp[u].push_back(v);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
            tarjan(i);
    }
    cout<<ans<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注