【HAOI2006】受欢迎的牛

题面

https://www.luogu.org/problem/P2341

题解

#include<iostream>
#include<vector>
#include<cstdio>
#include<stack>
#include<map>
#include<cstring>
const int inf=987654321;
using namespace std;
int n,m,a[10050],dfn[10050],low[10500],cloct,bel[10500],ru[10500],f[10500];
int u[100500],v[100500];
bool ins[10050],vis[10050];
vector<int> to[10050],about[10050];
map<int,bool> abo[10050];
stack<int> s;

void tarjan(int x){
  low[x]=dfn[x]=++cloct;
  s.push(x);
  ins[x]=true;
  int i,l=to[x].size(),t;
  for (i=0;i<l;i++) {
    if (ins[to[x][i]]) low[x]=min(low[x],dfn[to[x][i]]);
    else 
      if (dfn[to[x][i]]==0) {
        tarjan(to[x][i]);
        low[x]=min(low[x],low[to[x][i]]);
      }
  }
  if (low[x]==dfn[x]) {
    do {
      t=s.top();
      bel[t]=x;
      ins[t]=false;
      s.pop();
      if (t==x) break;
    } while (1);
  }
  return;
}

int main(){
  int i,j,uu,vv;
  scanf("%d %d",&n,&m);
  for (i=1;i<=m;i++) {
    scanf("%d %d",&u[i],&v[i]);
    to[u[i]].push_back(v[i]);
  }
  cloct=0;
  for (i=1;i<=n;i++) if (!dfn[i]) tarjan(i);
  for (i=1;i<=n;i++) a[bel[i]]++;
  for (i=1;i<=m;i++) {
    uu=bel[u[i]]; vv=bel[v[i]];
    if (uu!=vv && !abo[uu].count(vv)) {
      abo[uu][vv]=true;
      ru[uu]++;
      about[uu].push_back(vv);
    }
  }
  int cnt=0,ans;
  for (i=1;i<=n;i++) if (!ru[bel[i]] && !vis[bel[i]]) {
    vis[bel[i]]=true;
    cnt++;
    ans=a[bel[i]];
  }
  if (cnt==1) cout<<ans<<endl; else cout<<0<<endl;
}