POJ 3275 Ranking the Cows

問題

牛がN匹いて、それぞれの牛の牛乳の生産量は異なっている。2匹の牛の牛乳の生産量の大小を表すクエリがM個与えられる。生産量の順番を確定するために必要になる追加のクエリ数を求めよ。

やりかた

牛がN匹いるとすると順番を確定するための関係はになる。あたえられたM個のクエリのうち確定している関係の個数からこれを引いたものが答えになる。M個のクエリをグラフの構造にすると、あるノード（牛）に着目したときにそのノードより小さいノードの個数というのが、その牛より少ない生産量の牛との関係の個数を表す。これをすべてのノードについて計算すれば確定している関係性の個数が判定できる。小さいノードを調べるのは普通に深さ優先でいい。

以下ソース。

vector<int> g[1001];
bool vis[1001];

int dfs(int idx){
  int s = 0;
  vis[idx] = true;
  for(int i = 0; i < g[idx].size(); i++){
    int to = g[idx][i];
    if(!vis[to]) s += dfs(to) + 1;
  }
  return s;
}

int main(int argc, char **argv){
  FILL(header, -1);
  
  int N, M;
  scanf("%d %d", &N, &M);
  for(int i = 0; i < M; i++){
    int a, b;
    scanf("%d %d", &a, &b);
    a--, b--;
    g[a].push_back(b);
  }

  int s = 0;
  for(int i = 0; i < N; i++){
    FILL(vis, false);
    s += dfs(i);
  }

  printf("%d\n", N * (N - 1) / 2 - s);
  return 0;
}