package question;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Question947 {
 public static void main(String[] args) {
 int[][] ints = {
 {0, 0}, {0, 2}, {1, 1}, {2, 0}, {2, 2}
 };
 System.out.println(new Question947().removeStones2(ints));
 }

 public int removeStones2(int[][] stones) {
 UnionFind unionFind = new UnionFind();
 for (int[] stone : stones) {
 unionFind.merge(stone[0], stone[1]+10001);
 }
 return stones.length-unionFind.count;
 }

 private class UnionFind {
 Map<Integer, Integer> map;
 int count;

 public UnionFind() {
 map = new HashMap<>();
 }

 public int find(int x) {
 if (!map.containsKey(x)) {
 map.put(x, x);
 count++;
 }
 if (map.get(x)!=x) {
 map.put(x, find(map.get(x)));
 }
 return map.get(x);
 }

 public void merge(int x, int y) {
 x=find(x);
 y=find(y);
 if (x==y) return;
 map.put(x, y);
 count--;
 }
 }

 public int removeStones(int[][] stones) {
 int offset = 32;
 int b = Integer.MIN_VALUE;
 List<MySet> list = new ArrayList<>();

 for (int[] stone : stones) {
 int row = stone[0];
 int column = stone[1];
 int r1 = row / offset;
 int r2 = (b >>> (row & (offset-1)));
 int c1 = column / offset;
 int c2 = (b >>> (column & (offset-1)));
 int x = -1;
 int y = -1;
 for (int i = 0; i < list.size(); i++) {
 MySet set = list.get(i);
 if ((set.row[r1] & r2) != 0) x = i;
 if ((set.column[c1] & c2) != 0) y = i;
 if (x != -1 && y != -1) break;
 }
 if (x == -1 && y == -1) {
 MySet set = new MySet();
 set.row[r1] |= r2;
 set.column[c1] |= c2;
 list.add(set);
 } else if (x == -1)
 list.get(y).row[r1] |= r2;
 else if (y == -1)
 list.get(x).column[c1] |= c2;
 else if (x != y)
 merge(list.get(x), list.remove(y));
 }

 return stones.length - list.size();
 }

 private void merge(MySet a, MySet b) {
 for (int i = 0; i < MySet.N; i++) {
 a.row[i] |= b.row[i];
 a.column[i] |= b.column[i];
 }
 }
}

class MySet {
 int[] row;
 int[] column;
 public static final int N = 313;

 public MySet() {
 row = new int[N];
 column = new int[N];
 }
}