1
class Solution {
2
  int[] rank;
3
  int[] parent;
4
  int[] rival;
5

6
  public boolean possibleBipartition(int n, int[][] dislikes) {
7
    rank = new int[n + 1];
8
    rival = new int[n + 1];
9
    parent = new int[n + 1];
10
    for (int i = 1; i <= n; i++) {
11
      rank[i] = 1;
12
      parent[i] = i;
13
    }
14
    for (int[] dis : dislikes) {
15
      int x = dis[0], y = dis[1];
16
      if (find(x) == find(y)) return false;
17
      if (rival[x] != 0) union(rival[x], y);
18
      else rival[x] = y;
19
      if (rival[y] != 0) union(rival[y], x);
20
      else rival[y] = x;
21
    }
22
    return true;
23
  }
24

25
  public int find(int x) {
26
    if (parent[x] == x) return x;
27
    return parent[x] = find(parent[x]);
28
  }
29

30
  public void union(int x, int y) {
31
    int x_set = find(x);
32
    int y_set = find(y);
33
    if (x_set == y_set) return;
34
    if (rank[x_set] < rank[y_set]) parent[x_set] = y_set;
35
    else if (rank[y_set] < rank[x_set]) parent[y_set] = x_set;
36
    else {
37
      parent[x_set] = y_set;
38
      rank[y_set]++;
39
    }
40
  }
41
}