给定N(N<=10000)个点和M(M<=50000)条边(注意:是有向边),求有多少个受欢迎的点,当且仅当任何一个点出发都能到达它。
- 这道题可能会有环->缩环成点
- 无环的情况:
- 1:若有向无环图是连通的,只有出度为0的点才是“受欢迎的点”。
- 2:若有向无环图是连通的,当存在大于1个出度为0的点,则图中没有“受欢迎的点”。
- 寻找出度为0的点,如果不止一个,就没有答案,否则就是该点
//usaco 2003 popular
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int MN=;
int m,n;
vector<int>t[MN];
int outd[MN];//出度
int low[MN],dfn[MN],vis[MN],sum[MN],blong[MN];
int cnt,cntt;//点 分量
stack<int>s;
void tar(int x){
dfn[x]=low[x]=++cnt;
s.push(x);
vis[x]=;
int y;
for(vector<int>::iterator it=t[x].begin();it!=t[x].end();++it){
y=*it;
if(!dfn[y]){//dfn
tar(y);
low[x]=min(low[x],low[y]);
}
else if(vis[y]){//vis
low[x]=min(low[x],dfn[y]);//dfn
}
}
if(dfn[x]==low[x]){
++cntt;
do{
y=s.top();
s.pop();
sum[cntt]++;
blong[y]=cntt;
vis[y]=;
}while(y!=x);
}
}
int main(){
freopen("popular.in","r",stdin);
freopen("popular.out","w",stdout);
cin>>n>>m;
int ku,kv;
for(int i=;i!=m;i++){
cin>>ku>>kv;
t[ku].push_back(kv);
}
for(int i=;i<=n;i++){
if(!dfn[i]){
tar(i);
}
}
int flag=;
for(int i=;i<=n;i++){
for(vector<int>::iterator it=t[i].begin();it!=t[i].end();++it){
int j=*it;
if(blong[i]!=blong[j]){
outd[blong[i]]++;
}
}
}
for(int i=;i<=cntt;i++){
if(!outd[i]){
if(flag){
cout<<<<endl;
return ;
}
else flag=i;
}
}
if(flag)cout<<sum[flag]<<endl;
else cout<<<<endl;
return ;
fclose(stdin);
fclose(stdout);
}
有向图强连通分量的Tarjan算法