题解 P2341 【[HAOI2006]受欢迎的牛】

2018-05-27 11:45:19


大佬们都用的是tarjan,标签也是

并未说是kosaraju

但蒟蒻用kosaraju也写出来了


思路:求取强连通分量,缩点


如何求强连同分量?

强连通分量 —Kosaraju | Tarjan | Gabow

还有,求出强连通分量后如何判断出度为0的点?

其实可以再第二遍dfs时,由于是逆图,所以该的出度就等于入读

利用这一点可以打出代码,还有一些细节看下方


#include<bits/stdc++.h>//万能头文件
using namespace std;
#define MAXV 10010
#define MAXE 50010
#define For(i,j,n) for(int i=(j);i<=(n);++i)
//宏定义
int head[MAXV],n,m,top[MAXV],topsort,rhead[MAXV],ans[MAXV],cdans[MAXV];
bool book[MAXV];
stack<int>s;
struct E{int next,to;}e[MAXE],re[MAXE];
//初始化
void dfs(int i){
    if(book[i])return ;
    book[i]=1;
    int k=head[i];
    while(e[k].to){dfs(e[k].to);k=e[k].next;}
    s.push(i);
}
//kosrarju第一遍求图的逆后续排列
void rdfs(int i){
    if(book[i])return ;
    book[i]=1;top[i]=topsort;ans[topsort]++;
    int k=rhead[i];
    while(re[k].to){
        if(top[re[k].to]!=top[i]&&book[re[k].to])cdans[top[re[k].to]]++;
        else rdfs(re[k].to);
        k=re[k].next;
    }
}
//第二遍求强连通分量+缩点+求取强连通分量的出度
int main(){
    cin>>n>>m;
    For(i,1,m){
        int a,b;
        cin>>a>>b;
        e[i].to=b;e[i].next=head[a];head[a]=i;
        re[i].to=a;re[i].next=rhead[b];rhead[b]=i;
    }
    For(i,1,n)dfs(i);
    memset(book,0,sizeof(book));
    while(!s.empty()){
        if(!book[s.top()])topsort++;
        rdfs(s.top());
        s.pop();
    }
    int ansl=0;
    For(i,1,topsort)
        if(cdans[i]==0)
            if(ansl!=0){printf("0");return 0;}
            //如果有2个出度为0的点则,不可能
            else ansl=i;

    cout<<ans[ansl];
    return 0;
}