1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <string>
#include <map>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::map;
class UnionSet {
private:
  static const int kNotExist = -1;
  map<string, int> name_to_id_;
  int *parent_;
  int GetIndex(const string& name, bool create=false) {
    map<string, int>::iterator it = name_to_id_.find(name);
    if (it != name_to_id_.end()) return it->second;
    else if (create) {
      return name_to_id_[name] = name_to_id_.size();
    } else return kNotExist;
  }
  int GetParent(int idx) {
    int p_idx = idx;
    while (parent_[p_idx] != p_idx) {
      p_idx = parent_[p_idx];
    }
    while (parent_[idx] != idx) {
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX