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];
    }
}