一道强连通分量的裸题。
由题意,对于唯一出度为0的的强连通分量,我们可以认为其中所有的奶牛均是明星奶牛,而若存在两个出度为0的强连通分量则不存在明星奶牛。
我们通过Tarjan算法计算出强连通分量,对每个强连通分量进行染色并计算出度。
参考代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 50001;
int n, m;
int ind, gid;
int g[N], gn[N];
int low[N], dfn[N];
int ext[N];
bool instack[N];
stack<int> s;
vector<int> G[N];
int min(int a, int b) {
return a < b ? a : b;
}
void tarjan(int u) {
low[u] = dfn[u] = ++ind;
instack[u] = true;
s.push(u);
for ( auto v : G[u] ) {
if ( !dfn[v] ) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if ( instack[u] )
low[u] = min(low[u], dfn[v]);
}
if ( low[u] == dfn[u] ) {
++gid;
int cur;
do {
cur = s.top();
g[cur] = gid;
++gn[gid];
instack[cur] = false;
s.pop();
} while ( cur != u );
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
int u, v;
for ( int i = 1; i <= m; ++i ) {
cin >> u >> v;
G[u].push_back(v);
}
for ( int i = 1; i <= n; ++i )
if ( !dfn[i] )
tarjan(i);
for ( int u = 1; u <= n; ++u ) {
for ( auto v : G[u] )
if ( g[v] != g[u] )
++ext[g[u]];
}
int ans = 0;
for ( int i = 1; i <= gid; ++i )
if ( !ext[i] ) {
if ( ans ) {
cout << 0 << endl;
return 0;
}
ans = gn[i];
}
cout << ans << endl;
return 0;
}