题解 P2341 【[HAOI2006]受欢迎的牛】
vivarock
2018-05-27 11:45:19
大佬们都用的是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;
}
```
------------