题解 P2341 【[HAOI2006]受欢迎的牛】

这题是一道标准的强连通分量题，运用缩点的方法来做。 ~~其实我也花了很多时间弄懂这个瓜皮算法~~ 如果**只有一个缩点**的出度为0，就可以判断该缩点内的所有奶牛均为明星奶牛 如果**有两个以上的缩点**出度为0，那说明这两个缩点互不喜欢，所以没有奶牛是明星奶牛 **最后吐槽一句，图论的题目定级为何这么高233** ···cpp ```cpp #include<cstdio> #include<stack> using namespace std; struct node{ int next; int from,to; }edge[50010];//邻接表存储有向边 int len=0;//len表示邻接表的大小 int n,m,sum=0;//sum是dfn的大小 int head[10010],dfn[10010],low[10010],sin[10010],vis[10010];//head与邻接表有关，dfn是搜索的顺序，low是搜索到的点顺序的最小值，sin[x]表示x是否在栈内，vis[x]表示x是否搜索过 int colsize,scl[10010],col[10010],ind[10010];//colsize是缩点数组的数量，scl是每个缩点的大小，col[x]表示x属于哪个缩点，ind说明col的入度 stack <int> s;//栈 int rin(){//标准读入优化 int sum=0; char ch=getchar(); while (ch>'9'||ch<'0') ch=getchar(); while (ch<='9'&&ch>='0'){ sum=sum*10+ch-'0'; ch=getchar(); } return sum; } int fmin(int a,int b){return a<b?a:b;}//min函数 void add(int u,int v){//增加有向边 edge[++len].from=u; edge[len].to=v; edge[len].next=head[u]; head[u]=len; } void tarjan(int u){//tarjan算法 dfn[u]=low[u]=++sum; s.push(u); sin[u]=vis[u]=1; for (int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if (vis[v]==0){ tarjan(v); low[u]=fmin(low[u],low[v]); } else if (sin[v]==1) low[u]=fmin(low[u],dfn[v]); } if (dfn[u]==low[u]){ scl[col[u]=++colsize]=1; while (s.top()!=u){ scl[col[s.top()]=colsize]++; sin[s.top()]=0; s.pop(); } sin[u]=0; s.pop(); ``` }//最后处理完scl是该缩点的大小，然后栈内包括u的缩点的点退栈，col存储的是点属于哪一个缩点 ```cpp return; } void inpt(){//输入处理 n=rin(); m=rin(); for (int i=1;i<=n;i++) head[i]=-1; for (int i=1;i<=m;i++){ int a=rin(),b=rin(); add(b,a);//将有向边加入邻接表，但是这里边是反的方便处理出度将出度变为入度 } } void work(){//主要处理 for (int i=1;i<=n;i++) if (vis[i]==0) tarjan(i);//如果这个点没有访问过就tarjan for (int i=1;i<=n;i++) for (int j=head[i];j!=-1;j=edge[j].next) if (col[i]!=col[edge[j].to]) ind[col[edge[j].to]]++;//如果这个缩点有入边就增加该缩点的入度 } void outp(){//输出处理 int ans=0; for (int i=1;i<=colsize;i++){ if (ind[i]==0&&ans==0) ans=scl[i];//如果该缩点入度（出度）等于0并且只有一种这样的情况就代表该缩点里都是明星奶牛 else if(ind[i]==0) ans=-1;//否则就没有明星奶牛 } printf("%d\n",ans==-1?0:ans); } int main(){ inpt(); work(); outp(); return 0; } ··· ```