P2341 受欢迎的牛

问题

P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G
牛群中给出了若干“奶牛 $A$ 喜欢奶牛 $B$”的关系，而且喜欢关系具有传递性，每头奶牛也喜欢自己。一头明星奶牛必须受到所有奶牛喜欢，要求计算这样的奶牛共有多少头。

数据规模：$N\le 10^4$，$M\le 5\times 10^4$。

由于喜欢是单向的，同时具有传递性，所以会想到图论中的强连通分量。

然后使用 Tarjan 缩点，原图变成一张 DAG，问题转化为寻找能被所有缩点到达的分量。

发现如果某个 SCC 要被所有的 SCC 到达，那么它一定没有出度。而若 DAG 中有两个或更多的出度为 0 的汇点，它们之间无法相互抵达，就不存在要求的奶牛了。

反过来，若缩点 DAG 只有一个汇点，从任意节点沿出边不断前进，最终只能停在这个汇点，因此所有节点都会到达它。答案就是这个唯一零出度 SCC 的大小，否则答案为 $0$。

不过这题不需要显式建立缩点图，只要统计每个 SCC 的出度即可。Tarjan 和出度统计的总时间复杂度为 $O(N+M)$，空间复杂度同样为 $O(N+M)$。

▶

P2341 受欢迎的牛

struct Edge { int v; ll w; };
vector<Edge> adj[maxn];

int dfn[maxn], low[maxn], timer;
int scc[maxn], scnt;
int scc_siz[maxn];

int stk[maxn], top;
bool ins[maxn];

void tarjan( int u ) {
    dfn[u] = low[u] = ++ timer;
    stk[++ top] = u, ins[u] = true;

    for( auto [v, w] : adj[u] ) {
        if( !dfn[v] ) {
            tarjan( v );
            low[u] = min( low[u], low[v] );
        } else if( ins[v] ) {
            low[u] = min( low[u], dfn[v] );
        }
    }

    if( low[u] == dfn[u] ) {
        scnt ++; int v;
        do {
            v = stk[top --];
            ins[v] = 0;
            scc[v] = scnt;
            scc_siz[scnt] ++;
        } while( v != u );
    }
}

int oud[maxn];

void solve( ) {
    int n = read( ), m = read( );
    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        adj[u].push_back({ v, 0 });
    }

    for( int i = 1; i <= n; ++ i ) {
        if( !dfn[i] ) tarjan( i );
    }

    for( int u = 1; u <= n; ++ u ) {
        for( auto [v, w] : adj[u] ) {
            if( scc[u] != scc[v] ) oud[scc[u]] ++;
        }
    }

    int cnt = 0, ans = 0;
    for( int i = 1; i <= scnt; ++ i ) {
        if( oud[i] == 0 ) {
            cnt ++;
            ans = scc_siz[i];
        }
    }
    if( cnt == 1 ) cout << ans << '\n';
    else cout << 0 << '\n';
}

记录

• 归属：SCC 缩点；
• 新增：被所有点到达的节点恰好组成缩点 DAG 的唯一汇点 SCC，因此只需判断零出度分量是否唯一。
• 分类：待定