PKU 2186 Popular Cows

2186 -- Popular Cows

[問題]
M個のペア(A,B): 牛Aが牛Bを人気者だと思っている　が与えられる。ただし (A,B) ,(B,C) => (A,C) とする。(関係は推移的)
自分以外の全ての牛から人気者だと思われている牛の数を求めよ

ずっと放置していた蟻本の問題。

すべての牛から人気者だと思われている牛と同じ強連結成分に属する全ての牛もまたすべての牛から人気者だと思われている。

なので他の全ての強連結成分から到達可能な強連結成分に属する牛の数が答えとなる。

答えとなりうる集合はトポロジカル順序の一番最後の強連結成分なので、これを候補として挙げ、実際に全ての集合から到達可能かを確認すれば良い。

という事だと思う(あやふや...

強連結成分分解初めて書いた

const int MAX_V = 10001;
int V;
vector<int>G[MAX_V];
vector<int>rG[MAX_V];
vector<int>vs;
bool used[MAX_V];
int cmp[MAX_V];

void add_edge(int from,int to){
  G[from].pb(to);
  rG[to].pb(from);
}

void dfs(int v){
  used[v] = true;
  for(int i = 0; i < G[v].size(); i++)
    if(!used[G[v][i]]) dfs(G[v][i]);
  vs.pb(v); //帰りがけ順
  
}
void rdfs(int v,int k){
  used[v] = true;
  cmp[v] = k;
  for(int i = 0 ;i < rG[v].size();i++)
    if(!used[rG[v][i]]) rdfs(rG[v][i],k);
}
int scc(){
  memset(used,0,sizeof(used));
  vs.clear();
  for(int v = 0; v < V;v++)
    if(!used[v]) dfs(v);
  memset(used,0,sizeof(used));
  int k = 0;
  for(int i = vs.size() - 1; i >= 0; i--)
    if(!used[vs[i]]) rdfs(vs[i],k++);
  return k;
}
const int MAX_M = 50001;
int N,M;
int A[MAX_M],B[MAX_M];
void solve(){
  V = N;
  for(int i = 0; i < M; i++) add_edge(A[i] - 1,B[i] - 1);
  int n = scc();
  int u = 0,num = 0;
  for(int v = 0; v < V; v++){
    if(cmp[v] == n-1){//トポロジカル順序最後の強連結成分
      u = v;
      num++;
    }
  }
  memset(used,0,sizeof(used));
  rdfs(u,0);
  for(int v = 0; v < V; v++){
    if(!used[v]){
      num = 0;
      break;
    }
  }
  cout<<num<<endl;
}
int main(){
  cin>>N>>M;
  rep(i,M)
    cin>>A[i]>>B[i];
  solve();
}