C++ 优化技巧：解决奶牛明星问题 - 广度优先搜索 (BFS) 优化

#pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> using namespace std; inline static const nullptr_t _={ ios::sync_with_stdio(0); cin.tie(nullptr),cout.tie(nullptr); return nullptr; }(); int n,m,ans,sum; vector g[10005]; bitset<10005> vis; void bfs(int b,int t){ queue q; q.emplace(b); while(!q.empty()){ int f=q.front(); q.pop(); if(f==t){ sum++; vis.reset(); return; } for(int i=0;i<g[f].size();i++){ if(!vis[g[f][i]]){ vis[g[f][i]]=1; q.emplace(g[f][i]); } } } } int main() { cin>>n>>m; for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; g[u].emplace_back(v); } for(int i=1;i<=n;i++){ sum=0; for(int j=1;j<=n;j++) if(j!=i) vis[j]=1,bfs(j,i),vis[j]=0; if(sum==n-1) ans++; } cout<<ans<<'\n'; return 0; } 这道题目要求找出能成为明星奶牛的数量。明星奶牛是指被所有其他奶牛喜欢的奶牛。

一种简单的解法是对于每头奶牛，使用广度优先搜索（BFS）来判断它是否被其他所有奶牛喜欢。具体步骤如下：

1. 对于每头奶牛i，初始化一个计数器sum为0。
2. 对于每头不是i的奶牛j，将奶牛j标记为已访问（vis[j]=1），然后从奶牛j开始进行BFS。
3. 在BFS中，使用一个队列q来存储已访问的奶牛。初始时将奶牛j加入队列。
4. 在每次循环中，取出队列的头部元素f，如果f等于奶牛i，则说明奶牛i被奶牛j喜欢，将sum加1，并将vis数组重置为0。
5. 遍历奶牛f的所有相邻奶牛，如果该奶牛未被访问过，则将其标记为已访问，并加入队列。
6. 重复步骤4-5，直到队列为空。
7. 如果sum等于N-1（其中N为奶牛的总数），则说明奶牛i被所有其他奶牛喜欢，将ans加1。
8. 重复步骤2-7，遍历所有的奶牛。
9. 输出ans。

这种解法的时间复杂度为O(N^2 * M)，其中N为奶牛的总数，M为爱慕关系的数量。

然而，这种解法在面对大规模的输入数据时会超时。为了优化算法的效率，我们可以使用一种优化技巧，即预处理所有奶牛的喜欢关系。

具体优化步骤如下：

1. 定义一个二维数组g，g[i]表示奶牛i喜欢的所有奶牛。
2. 对于每个爱慕关系(A, B)，将B加入g[A]中。
3. 遍历所有的奶牛，对于每头奶牛i，使用BFS来判断它是否被其他所有奶牛喜欢。
4. 在BFS中，使用一个队列q来存储已访问的奶牛。初始时将除了i以外的所有奶牛j加入队列。
5. 在每次循环中，取出队列的头部元素f，如果f等于奶牛i，则说明奶牛i被奶牛j喜欢，将sum加1，并将vis数组重置为0。
6. 遍历奶牛f的所有相邻奶牛，如果该奶牛未被访问过，则将其标记为已访问，并加入队列。
7. 重复步骤5-6，直到队列为空。
8. 如果sum等于N-1（其中N为奶牛的总数），则说明奶牛i被所有其他奶牛喜欢，将ans加1。
9. 输出ans。

这种优化后的解法的时间复杂度为O(N * M)，可以满足题目要求的时空限制。