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

vivarock

2018-05-27 11:45:19

Solution

大佬们都用的是tarjan,标签也是 并未说是kosaraju #但蒟蒻用kosaraju也写出来了 ------------ # 思路:求取强连通分量,缩点 ------------ 如何求强连同分量? [强连通分量 —Kosaraju | Tarjan | Gabow](https://juruo-oier.blog.luogu.org/qiang-lian-tong-fen-liang-kosaraju-tarjan-gabow) 还有,求出强连通分量后如何判断出度为0的点? 其实可以再第二遍dfs时,由于是逆图,所以该的出度就等于入读 利用这一点可以打出代码,还有一些细节看下方 ------------ ```cpp #include<bits/stdc++.h>//万能头文件 using namespace std; #define MAXV 10010 #define MAXE 50010 #define For(i,j,n) for(int i=(j);i<=(n);++i) //宏定义 int head[MAXV],n,m,top[MAXV],topsort,rhead[MAXV],ans[MAXV],cdans[MAXV]; bool book[MAXV]; stack<int>s; struct E{int next,to;}e[MAXE],re[MAXE]; //初始化 void dfs(int i){ if(book[i])return ; book[i]=1; int k=head[i]; while(e[k].to){dfs(e[k].to);k=e[k].next;} s.push(i); } //kosrarju第一遍求图的逆后续排列 void rdfs(int i){ if(book[i])return ; book[i]=1;top[i]=topsort;ans[topsort]++; int k=rhead[i]; while(re[k].to){ if(top[re[k].to]!=top[i]&&book[re[k].to])cdans[top[re[k].to]]++; else rdfs(re[k].to); k=re[k].next; } } //第二遍求强连通分量+缩点+求取强连通分量的出度 int main(){ cin>>n>>m; For(i,1,m){ int a,b; cin>>a>>b; e[i].to=b;e[i].next=head[a];head[a]=i; re[i].to=a;re[i].next=rhead[b];rhead[b]=i; } For(i,1,n)dfs(i); memset(book,0,sizeof(book)); while(!s.empty()){ if(!book[s.top()])topsort++; rdfs(s.top()); s.pop(); } int ansl=0; For(i,1,topsort) if(cdans[i]==0) if(ansl!=0){printf("0");return 0;} //如果有2个出度为0的点则,不可能 else ansl=i; cout<<ans[ansl]; return 0; } ``` ------------