[HAOI2006]受欢迎的牛

https://www.lydsy.com/JudgeOnline/problem.php?id=1051

https://www.luogu.org/problemnew/show/P2341

题意：算出有多少头奶牛可以当明星。

题解：强连通分量

由题可得，受欢迎的奶牛只有可能是图中唯一的出度为零的强连通分量中的所有奶牛，所以若出现两个以上出度为0的强连通分量则不存在明星奶牛，因为那几个出度为零的分量的爱慕无法传递出去。那唯一的分量能受到其他分量的爱慕同时在分量内相互传递，所以该分量中的所有奶牛都是明星。

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum,top,col;
int a,b,c,sta[N],vis[N],low[N],dfn[N],si[N],co[N],de[N];
vector<int>G[N];
void Tarjan(int u){
    dfn[u]=low[u]=++sum;
    vis[u]=1;
    sta[++top]=u;
    for(int i=0,j=G[u].size();i<j;i++){
        int v=G[u][i];
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[v],low[u]);
        }else if(vis[v]){
            low[u]=min(dfn[v],low[u]);
        }
    }
    if(dfn[u]==low[u]){
        co[u]=++col;
        ++si[col];
        while(sta[top]!=u){
            ++si[col];
            co[sta[top]]=col;
            vis[sta[top]]=0;
            --top;
        }
        vis[sta[top]]=0;
        --top;
    }

}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        G[b].push_back(a);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
    for(int i=1;i<=n;i++)
        for(int j=0,k=G[i].size();j<k;j++)
            if(co[i]!=co[G[i][j]])
                de[co[G[i][j]]]++;
    for(int i=1;i<=col;i++)if(!de[i])ans=si[i],cnt++;
    cout<<(cnt==1?ans:0)<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

题解：kosaraju算法

一个反图，从最后那个强连通分量中随便找一个点，然后进行反图遍历

如果所有的点都被访问过了，证明最后一个强连通分量中的点都是明星牛，如果访问不到，则说明没有牛是明星

#include <bits/stdc++.h>
using namespace std;
#define maxn 10010
int m,n,nl,mmp,sum;
vector<int> G[maxn];
vector<int> RG[maxn];
vector<int> vs;
bool used[maxn];
int cmp[maxn];
void add(int a,int b)//两个邻接表存储 
{
    G[a].push_back(b);//正图 
    RG[b].push_back(a);//反图 
}
void dfs(int v)//第一遍搜索； 
{
    used[v]=1;
    for(int i=0;i<G[v].size();i++)
    {
        if(!used[G[v][i]])
        dfs(G[v][i]);
    }
    vs.push_back(v);
}
void rdfs(int v,int k)//第二遍搜索 
{
    used[v]=1;
    cmp[v]=k;
    for(int i=0;i<RG[v].size();i++)
    {
        if(!used[RG[v][i]])
        rdfs(RG[v][i],k);
    }
}
int scc()
{
    memset(used,0,sizeof(used));
    vs.clear();
    for(int i=1;i<=n;i++)
    if(!used[i])
    dfs(i);
    memset(used,0,sizeof(used));
    int k=0;
    for(int i=vs.size()-1;i>=0;i--)
    if(!used[vs[i]])
    rdfs(vs[i],k++);
    return k;
}
int DFS(int haha)//其实这个搜索可以直接用第二个（rdfs）替代，不过这样看起来比较清楚。。。。。。 
{
    used[haha]=1;
    for(int i=0;i<RG[haha].size();i++)
    {
        if(!used[RG[haha][i]])
        DFS(RG[haha][i]);
    }
}
int main()
{
    int u,p;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    cin>>u>>p,add(u,p);
    int ans=scc();
    //cout<<ans<<endl;
    for(int i=1;i<=n;i++)
    {
    if(cmp[i]==ans-1)//注意这里ans要减一； 
        {
            mmp=i;
            sum++;
        }
    }
    memset(used,0,sizeof(used));
    rdfs(mmp,1);
    for(int i=1;i<=n;i++)//看一下是否所有点都被访问过了 
    {
        if(!used[i])
        {
            cout<<0<<endl;
            return 0;
        }
    }
    cout<<sum<<endl;//如果都被访问过了则最后一个强连通分量里的牛牛都是明星，输出即可； 
    return 0;
}