洛谷P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G 题解

# 洛谷P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G 题解

题目链接：P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

题意：

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 \(A\) 喜欢 \(B\)，\(B\) 喜欢 \(C\)，那么 \(A\) 也喜欢 \(C\)。牛栏里共有 \(N\) 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

对于 \(100\%\) 的数据，\(1\le N\le10^4\)，\(1\le M\le5\times 10^4\)。

首先考虑最简单的情况

如果给定的是一个DAG（有向无环图）

当且仅当存在两个及以上出度为 \(0\) 的结点时，答案为 \(0\) （无解）

但是题目给的不一定是DAG

注意到每个强连通分量内的结点两两可达

用这题的语言就是，某个强连通分量内的所有结点可以同时为“明星”

于是考虑强连通分量缩点，接下来就是DAG的情况了

注意此时的答案，如果有解的话，就是那个点对应的强连通分量大小

时间复杂度 \(O(n+m)\) ，采用 \(\text{kosaraju}\) 算法

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e4+15)

vector<int> g1[N],g2[N];
int n,m,cnt,scnt,scc[N],out[N],sz[N],dfn[N],vis[N];
void addEdge1(int u,int v)
{
    g1[u].push_back(v);
    g2[v].push_back(u);
}
void dfs1(int u)
{
    vis[u]=1;
    for(int v : g1[u])
        if(!vis[v]) dfs1(v);
    dfn[++cnt]=u;
}
void dfs2(int u,int id)
{
    scc[u]=id; ++sz[id];
    for(int v : g2[u])
        if(!scc[v]) dfs2(v,id);
}
void kosaraju()
{
    for(int i=1; i<=n; i++)
        if(!vis[i]) dfs1(i);
    scnt=0;
    for(int i=n; i>=1; i--)
        if(!scc[dfn[i]])
        {
            ++scnt;
            dfs2(dfn[i],scnt);
        }

}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,u,v; i<=m; i++)
    {
        cin >> u >> v;
        addEdge1(u,v);
    }
    kosaraju();
    for(int i=1; i<=n; i++)
        for(int j : g1[i])
        {
            int u=scc[i],v=scc[j];
            if(u!=v) ++out[u];
        }
    int p=0;
    for(int i=1; i<=scnt; i++)
    {
        if(out[i]) continue;
        if(p) return cout << 0,0;
        p=i;
    }
    cout << sz[p] << '\n';
    return 0;
}