usaco 月赛 2003 Fall Popular Cows 受欢迎的奶牛 题解

Description

Input

Output

Sample Input

3 3
1 2
2 1
2 3

Sample Output

1

Hint

Source

【大意】给定N（N<=10000)个点和M（M<=50000)条边（注意：是有向边），求有多少个“受欢迎的点”。所谓的“受欢迎的点”当且仅当任何一个点出发都能到达它。

【首先发现】99%的人都会想到直接用floyed来求。可惜的是，N太大了。我们再考虑新的算法。

【分析】让人厌烦的是，这道题可能会有环，即A--B,B--C,C--A。

先考虑无环的情况。定理1：若有向无环图是连通的，只有出度为0的点才是“受欢迎的点”。

伪证明：设某点X是“受欢迎的点”，且该点仍有出度。不妨设它能到达Y点。因为是有向无环图，那么Y是一定不能到达X点了！即X点并不是“受欢迎的点”——与条件矛盾，命题得证。

定理2：若有向无环图是连通的，当存在大于1个出度为0的点，则图中没有“受欢迎的点”。

伪证明：设点X和点Y是出度为0的点，那么X不能到达Y。命题得证。

【小结】太容易了吧！我们只要寻找出度为0的点，如果不止一个，就没有答案，否则就是那个点！

【深入思考】下面我们的任务就是要缩环成点。著名的Tarjan算法跳出来了！它的效率是O（N+M），太厉害了！（如果不知道Tarjan的实现过程，点击这里）那么只要在找到每一个强连通分量之后，对它中的每一个点并查集维护一下，就能缩成一个点了。

【注意点】①数量大，要用边表来记录。

②调用Tarjan算法时，要循环每一个点。一开始我一直WA，就是因为只从1号点进入递归。

【代码】

#include<stdio.h>
#include<cstring>
using namespace std;
const int v=10000+5;const int e=50000+5;
struct arr{int went,next;}a[e];
int begin[v],end[v],b[v],dfs[v],low[v],f[v];
bool flag[v],zhan[v],bre,ff[v];
int deep,step,n,m,i,x,y,cnt,j,go,temp,ans;
void make_up(int u,int v)                    //边表
{
  a[++cnt].went=v;
  if (begin[u]==0) {begin[u]=cnt;end[u]=cnt;}
  else {a[end[u]].next=cnt;end[u]=cnt;}
}
int get(int u){if (u==f[u]) return u;return f[u]=get(f[u]);}  //并查集
void Union(int u,int v){int uu=get(u);int vv=get(v);f[vv]=uu;}
void print(int k)                          //缩点
{
  int fa=b[deep];zhan[fa]=false;
  deep--;if (fa==k) return;
  while (1)
  {
    int i=b[deep];
    Union(fa,i);
    zhan[i]=false;
    deep--;
    if (i==k) break;
  }
}
void find(int k)                           //Tarjan
{
  dfs[k]=low[k]=++step;
  flag[k]=true;b[++deep]=k;zhan[k]=true;
  for (int i=begin[k];i!=0;i=a[i].next)
  {
    int go=a[i].went;
    if (!flag[go])
    {
      find(go);if (low[go]<low[k]) low[k]=low[go];
    }
    if ((zhan[go])&&(dfs[go]<low[k])) low[k]=dfs[go];
  }
  if (dfs[k]==low[k]) print(k);
}
int main()
{
  freopen("popular.in","r",stdin);
  freopen("popular.out","w",stdout);
  scanf("%ld%ld",&n,&m);
  for (i=1;i<=m;i++)
  {
    scanf("%ld%ld",&x,&y);
    make_up(x,y);
  }
  step=0;deep=1;b[1]=1;zhan[1]=true;
  for (i=1;i<=n;i++) f[i]=i;
  for (i=1;i<=n;i++)
    if (!flag[i]) find(i);
  cnt=0;
  for (i=1;i<=n;i++)
  {
    j=begin[i];bre=false;
    while (j!=0)
    {
      go=a[j].went;
      if (get(i)!=get(go)) {bre=true;break;}
      j=a[j].next;
    }
    if (bre) ff[get(i)]=true;
  }
  for (i=1;i<=n;i++)
    if ((f[i]==i)&&(!ff[i])) 
    {
      cnt++;temp=i;
    }
  if (cnt!=1) {printf("0");return 0;}
  for (i=1;i<=n;i++)
    if (get(i)==temp) ans++;
  printf("%ld",ans);
  return 0;
}

usaco 月赛 2003 Fall Popular Cows 受欢迎的奶牛 题解,布布扣,bubuko.com

usaco 月赛 2003 Fall Popular Cows 受欢迎的奶牛 题解

原文：http://blog.csdn.net/jiangshibiao/article/details/20913107