UVa10858 Nature

問題
http://uva.onlinejudge.org/external/108/10858.html

意訳
生物名が複数種与えられる。与えられた関係から食物連鎖に関わるグループを部類分けできるので、そのときの食物連鎖のグループの最大サイズを出力せよ。ただしAがBを捕食する関係にあるとき、同じ食物連鎖の族に分類される。

解法
UnionFindして、それぞれのノードが受け持つ親ノードに対してカウントするとサイズが求まる。

反省
親ノードに対してカウントするということだけがすぐに思いつかず何故かアイデアを部活終了直前まで放棄したせいで、部活中に解けなかった。（とは言っても失敗の半分はUVaが止まってたのが悪い）
自分がここまでなら分かっててここまでがわからないとか、常に意識しておくと簡単な事を見落とさなくなるかもしれない。

英文に関して、食物連鎖の直線距離だけを考えるわけではなくグラフのサイズと考える理由は、creaturesから分類されるgroupという表現やAはBを捕食するとき同じ食物連鎖のchainに含まれるという条件から捉えることが出来た。

#include <bits/stdc++.h>

using namespace std;

class UnionFind
{
public:
   
  vector<int> par, rank;
   
  UnionFind(int nn) {
    par.resize(nn), rank.resize(nn);
    for(int i=0; i<nn; i++) {
      par[i] = i;
      rank[i] = 0;
    }
  }
   
  int find(int x) {
    if(par[x] == x) return x;
    else return par[x] = find(par[x]);
  }
   
  void unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return;
     
    if(rank[x] < rank[y]) par[x] = y;
    else {
      par[y] = x;
      if(rank[x] == rank[y]) rank[x] ++;
    }
  }
   
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};
 
int main() {
 
  int C, R;
   
  while(cin >> C >> R && C) {
     
    map<string, int> cre;
     
    for(int i=0; i<C; i++) {
      string s; cin >> s;
      cre[s] = i;
    }
 
    UnionFind uf(C);
    for(int i=0; i<R; i++) {
      string s, t; cin >> s >> t;
      int a = cre[s], b = cre[t];
      uf.unite(a, b);
    }
     
    int cnt[5001] = {};
    for(int i=0; i<C; i++) {
      cnt[uf.find(i)] ++;
    }
    
    int ans = 0;
    for(int i=0; i<C; i++) {
      ans = max(ans, cnt[i]);
    }
    
    cout << ans << endl;
  }
  
  return 0;
}