BZOJ1051 [HAOI2006]受欢迎的牛 Tarjan 强连通缩点

时间:2024-09-02 17:07:20

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解


题目传送门 - BZOJ1051


题意概括

  有n只牛,有m个羡慕关系。

  羡慕关系具有传递性。

  如果A羡慕B,B羡慕C,那么我们认为A也羡慕C。

  问有多少牛被所有其他牛羡慕。


题解

  这次做这题我已经是第三遍了。

  USACO经典老题啊!(奶牛)

  POJ上面也有,叫popular cow。

  做法:

  先Tarjan强连通缩个点。

  然后,统计下入度。

  统计入度为0的点数。如果点数大于1,那么答案明显是0。

  如果点数是1,那么答案就是唯一的入度为0的点在缩点前点的个数。


代码

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=+,M=+;
struct Gragh{
int cnt,x[M],y[M],nxt[M],fst[N];
void set(){
cnt=;
memset(fst,,sizeof fst);
}
void add(int a,int b){
x[++cnt]=a,y[cnt]=b;
nxt[cnt]=fst[a],fst[a]=cnt;
}
}g;
int n,m;
int dfn[N],low[N],st[N],time,ans,top,bh[N],cnt[N];
bool inst[N],vis[N];
void Tarjan_Prepare(){
time=ans=top=;
memset(bh,,sizeof bh);
memset(st,,sizeof st);
memset(dfn,,sizeof dfn);
memset(low,,sizeof low);
memset(vis,,sizeof vis);
memset(inst,,sizeof inst);
}
void Tarjan(int x){
dfn[x]=low[x]=++time;
vis[x]=inst[x]=;
st[++top]=x;
for (int i=g.fst[x];i;i=g.nxt[i])
if (!vis[g.y[i]]){
Tarjan(g.y[i]);
low[x]=min(low[x],low[g.y[i]]);
}
else if (inst[g.y[i]])
low[x]=min(low[x],low[g.y[i]]);
if (low[x]==dfn[x]){
ans++;
bh[st[top]]=ans;
inst[st[top]]=;
while (st[top--]!=x){
bh[st[top]]=ans;
inst[st[top]]=;
}
}
}
int main(){
g.set();
scanf("%d%d",&n,&m);
for (int i=,a,b;i<=m;i++){
scanf("%d%d",&a,&b);
g.add(a,b);
}
Tarjan_Prepare();
for (int i=;i<=n;i++)
if (!vis[i])
Tarjan(i);
memset(cnt,,sizeof cnt);
for (int i=;i<=m;i++)
if (bh[g.x[i]]!=bh[g.y[i]])
cnt[bh[g.x[i]]]++;
int which=-;
for (int i=;i<=ans;i++)
if (cnt[i]==){
if (which!=-){
printf("");
return ;
}
which=i;
}
int Ans=;
for (int i=;i<=n;i++)
if (bh[i]==which)
Ans++;
printf("%d",Ans);
return ;
}