P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G（缩点）

发布时间：2025-08-20 04:56

P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

题目背景

本题测试数据已修复。

题目描述

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

输入格式

第一行：两个用空格分开的整数：和。

接下来行：每行两个用空格分开的整数：和，表示喜欢。

输出格式

一行单独一个整数，表示明星奶牛的数量。

输入输出样例 #1

输入 #1

3 3 1 2 2 1 2 3

输出 #1

说明/提示

只有号奶牛可以做明星。

【数据范围】

对于的数据，，。

对于的数据，，。
这道题就像将在处于一强连通分量的点揉成一个点，如果各个连通分量可以首尾相连形成一个长串，那么串上最后一个强连通分量团里奶牛的个数就是答案，答案是统计出度为零的团，我灵机一动改成了出度不为零，但错了，因为有的团出度和入度都不为零，我写博客时又想到如果缩点之后有两个互相独立的团怎么办，但很快我就想通了，如果有两个独立的团，就有两个团的出度为零，因为强连通分量视为没有出度，这时候就会被特判掉，为什么出度为零的点在两个或以上就不行呢，因为如果有两个说明这两个团只能有其他团到达，但从一个团是不可能同时到达这两个团的

#include<iostream> #include<vector> #include<stack> #define int long long using namespace std; const int N=1e5+5; int n,m,a,b,cnt=0,t=0,ans=0,num=0; int low[N],dfsn[N],vis[N],scc[N],sz[N],inc[N],outc[N]; vector<int>v[N]; stack<int>s; void dfs(int x){ low[x]=dfsn[x]=++t; vis[x]=1,s.push(x); for(int y:v[x]){ if(!dfsn[y]){ dfs(y); low[x]=min(low[x],low[y]); } else if(vis[y])low[x]=min(low[x],dfsn[y]); } if(low[x]==dfsn[x]){ cnt++; while(s.top()!=x){ vis[s.top()]=0; scc[s.top()]=cnt; sz[cnt]++; s.pop(); } vis[s.top()]=0; scc[s.top()]=cnt; sz[cnt]++; s.pop(); } } signed main(){ cin>>n>>m; while(m--){ cin>>a>>b; v[a].push_back(b); } for(int i=1;i<=n;i++)if(!dfsn[i])dfs(i); for(int x=1;x<=n;x++){ for(int y:v[x]){ if(scc[x]!=scc[y]){ inc[scc[y]]++; outc[scc[x]]++; } } } for(int i=1;i<=cnt;i++){ if(!outc[i]){ ans+=sz[i]; num++; } } if(num>1)cout<<0; else cout<<ans; return 0; }

网址：P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G（缩点） https://mxgxt.com/news/view/1696180

⬅️上一篇：Lisa手机壁纸惊现LV三公子，

➡️下一篇：公司开业想找明星录制祝福视频，怎