UVa11870 Antonyms

問題文
http://uva.onlinejudge.org/external/118/11870.html

概要
テストで英単語の同義語と対義語の試験が出る。対策の手間を省くために、単語の対義語の対義語が元の単語の同義語である場合、少ない関係を覚えるだけで覚えていない単語同士の関係も導き出せると考えた。

しかし、単語の対義語の対義語であっても、元の単語と対義語になってしまう場合がある。この場合は上述の法則を適用できない。

単語の関係が与えられたとき、法則が適用できるかどうか判定せよ。

なお、対義語の対義語であっても、全く別の単語であり同義語とはならないということが英語では起こりうるが、そのような関係性を指摘する意地悪なテストは出題されないので気にする必要はない。

解法
（以下のサイトと同じ）
http://rsujskf.blog32.fc2.com/blog-entry-1657.html

反省
色ペンで図を色々書いてみると多分解法が見つかる。多分というのは、自分がUnionFind同士のエッジの図やら２色彩色の図やらを書いていたのに、うまく詰められず上のサイト見てからコードを書いたから。

#include <bits/stdc++.h>
using namespace std;

#define allof(x) (x).begin(), (x).end()

struct UnionFind{

  std::vector<int> data;
  
  UnionFind(int size): data(size, -1){ }

  bool unite(int x, int y){
    x=root(x); y=root(y);
    if( x != y ){
      data[y] = x;
    }
    return x!=y;
  }

  bool find(int x, int y){
    return root(x) == root(y);
  }

  int root(int x){
    return (data[x] < 0)? x : data[x]=root(data[x]);
  }

};

vector<int> G[1010];

void add_edge(UnionFind& uf, int a, int b) {
  int x = uf.root(a), y = uf.root(b);
  if(find(allof(G[x]), y) == G[x].end()) {
    G[x].push_back(y);
  }
  if(find(allof(G[y]), x) == G[y].end()) {
    G[y].push_back(x);
  }
}

map<int, bool> used;

bool dfs(int idx, bool col) {
  
  used[idx] = col;
  
  for(int i=0; i<(int)G[idx].size(); i++) {
    if(used.find(G[idx][i]) == used.end()) {
      if(!dfs(G[idx][i], !col)) return false;
    }
    else {
      if(used[G[idx][i]] != col) {}
      else { return false; }
    }
  }
  
  return true;
}

int main() {
  
  int Tc; cin >> Tc;
  for(int Tcnt=1; Tcnt<=Tc; Tcnt++) {
    for(int i=0; i<1010; i++) G[i].clear();
    map<string, int> widx;
    int idx = 0;
    
    int N, M; cin >> N >> M;
    UnionFind uf(2*N+2*M);
    
    for(int i=0; i<N; i++) {
      string lhs, rhs; cin >> lhs >> rhs;
      if(!widx.count(lhs)) {
        widx[lhs] = idx ++;
      }
      if(!widx.count(rhs)) {
        widx[rhs] = idx ++;
      }
      uf.unite(widx[lhs], widx[rhs]);
    }
    
    int start;
    for(int i=0; i<M; i++) {
      string lhs, rhs; cin >> lhs >> rhs;
      if(!widx.count(lhs)) {
        widx[lhs] = idx ++;
      }
      if(!widx.count(rhs)) {
        widx[rhs] = idx ++;
      }
      start = widx[lhs];
      add_edge(uf, widx[lhs], widx[rhs]);
    }
    
    used.clear();
    cout << "Case " << Tcnt << ": "
         << (dfs(uf.root(start), true) ? "YES" : "NO")
         << endl;
  }
  
  return 0;
}