本文共 1948 字，大约阅读时间需要 6 分钟。

为了解决这个问题，我们需要找到被所有牛认为受欢迎的牛的数量。由于流行是传递的，我们可以使用图论中的强连通分量（SCC）来解决这个问题。

方法思路

解决代码

#include 
   
    #include 
    
     #include 
     
      using namespace std;int N, M;vector
      
       
        > adj, r_adj;vector
        
          scc_id, component_order;stack
         
           stk;void dfs1(int u) { if (scc_id[u] != 0) return; scc_id[u] = ++component_count; stk.push(u); for (int v : adj[u]) { if (scc_id[v] == 0) dfs1(v); }}void dfs2(int u) { for (int v : adj[u]) { if (scc_id[v] == 0) dfs2(v); } stk.push(u);}int main() { cin >> N >> M; adj.resize(N + 1); r_adj.resize(N + 1); for (int i = 1; i <= M; ++i) { int a, b; cin >> a >> b; adj[a].push_back(b); r_adj[b].push_back(a); } scc_id.resize(N + 1, 0); component_order.clear(); for (int u = 1; u <= N; ++u) { if (scc_id[u] == 0) dfs1(u); } while (!stk.empty()) { int u = stk.top(); stk.pop(); component_order.push_back(u); } component_count = component_order.size(); for (int u = 1; u <= N; ++u) { scc_id[u] = component_order[u]; } is_root.resize(component_count + 1, true); for (int u = 1; u <= N; ++u) { for (int v : r_adj[u]) { if (scc_id[u] != scc_id[v]) { if (is_root[scc_id[v]]) { is_root[scc_id[v]] = false; } } } } int root_count = 0; for (int i = 1; i <= component_count; ++i) { if (is_root[i]) { root_count++; } } if (root_count == 1) { int size = 0; for (int u = 1; u <= N; ++u) { if (scc_id[u] == component_count) { size++; } } cout << size; } else { cout << 0; }}
         
        
       
      
     
    
   

代码解释

这种方法通过找到根SCC来确定最终的答案，确保了高效性和准确性。