# On a 2D plane, we place stones at some integer coordinate points.  Each coordinate point may have at most one stone.
#
# Now, a move consists of removing a stone that shares a column or row with another stone on the grid.
#
# What is the largest possible number of moves we can make?
#
#
#
# Example 1:
#
# Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
# Output: 5
# Example 2:
#
# Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
# Output: 3
# Example 3:
#
# Input: stones = [[0,0]]
# Output: 0
#
#
# Note:
#
# 1 <= stones.length <= 1000
# 0 <= stones[i][j] < 10000
import collections


class UnionFind(object):
    def __init__(self, n):
        self.__group = range(n)
        self.size = [1] * n

    def find(self, x):
        while x != self.__group[x]:
            self.__group[x] = self.__group[self.__group[x]]
            x = self.__group[x]

        return x

    def union(self, x, y):
        x_group, y_group = map(self.find, (x, y))  # review how to use map
        if x_group != y_group:
            if self.size[x_group] >= self.size[y_group]:
                self.__group[y_group] = x_group
                self.size[x_group] += self.size[y_group]
                # self.size[y_group] = 1  # bugfixed
            else:
                self.__group[x_group] = y_group
                self.size[y_group] += self.size[x_group]
                # self.size[x_group] = 1  # bugfixed


# youtube - https://youtu.be/6WDkTVZUAsU


class Solution(object):
    def removeStones(self, stones):
        """
        :type stones: List[List[int]]
        :rtype: int
        """
        n = len(stones)
        uf = UnionFind(n)

        for i in xrange(1, n):
            for j in xrange(0, i):
                if stones[i][0] == stones[j][0] or (stones[i][1] == stones[j][1]):
                    uf.union(i, j)

        res = 0
        for i in xrange(n):
            res += uf.size[i] - 1

        return res

    def removeStones2(self, stones):
        """
        :type stones: List[List[int]]
        :rtype: int
        """
        n = len(stones)
        uf = UnionFind(n)

        for i in xrange(1, n):
            for j in xrange(0, i):
                if stones[i][0] == stones[j][0] or (stones[i][1] == stones[j][1]):
                    uf.union(i, j)

        return n - len({uf.find(i) for i in xrange(n)})

    def removeStones3(self, stones):
        """
        :type stones: List[List[int]] :rtype: int
        """

        n = len(stones)
        uf = UnionFind(20000)

        for x, y in stones:
            # why we need y+10001 here insted of just y
            # for case[[0,1],[1,0]], we will fistly connect 0->1, then we will connect 1->0
            # here y-coordinate happens to be the same as last one's x
            # so we add 10001 to avoid the overlap
            # why it is 10000, because we have 0 <= stones[i][j] < 10000
            # so add 10000 could gurantee there is no overlap

            uf.union(x, y + 10000)

        return n - len({uf.find(x) for x, y in stones})

    # using dfs
    def removeStones4(self, stones):
        """
        :type stones: List[List[int]]
        :rtype: int
        """
        rows, cols, seen = collections.defaultdict(set), collections.defaultdict(set), set()

        for row, col in stones:
            # same reason as the above uf method
            col = col + 10000
            rows[row].add((row, col))
            cols[col].add((row, col))

        st, res = [], 0
        for row in rows:
            for r, c in rows[row]:
                if (r, c) not in seen:
                    cnt = 0
                    st.append((r, c))
                    while st:
                        a, b = st.pop()
                        if (a, b) not in seen:
                            cnt += 1
                            seen.add((a, b))
                            for nei in rows[a]:
                                st.append(nei)
                            for nei in cols[b]:
                                st.append(nei)
                    res += cnt - 1

        return res





if __name__ == '__main__':
    # print Solution().removeStones([[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]])
    # print Solution().removeStones([[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]])
    # print Solution().removeStones([[0, 0]])
    # print Solution().removeStones([[0, 1], [1, 2], [1, 3], [3, 3], [2, 3], [0, 2]])
    print Solution().removeStones2([[0, 1], [1, 2], [1, 3], [3, 3], [2, 3], [0, 2]])
    print Solution().removeStones3([[0, 1], [1, 2], [1, 3], [3, 3], [2, 3], [0, 2]])
    print Solution().removeStones4([[0, 1], [1, 2], [1, 3], [3, 3], [2, 3], [0, 2]])
    # print Solution().removeStones([[6, 4], [0, 0], [2, 0], [5, 6], [3, 1], [1, 4], [1, 5], [0, 5], [1, 0], [5, 3]])
    print Solution().removeStones2([[6, 4], [0, 0], [2, 0], [5, 6], [3, 1], [1, 4], [1, 5], [0, 5], [1, 0], [5, 3]])
    print Solution().removeStones3([[6, 4], [0, 0], [2, 0], [5, 6], [3, 1], [1, 4], [1, 5], [0, 5], [1, 0], [5, 3]])
    print Solution().removeStones4([[6, 4], [0, 0], [2, 0], [5, 6], [3, 1], [1, 4], [1, 5], [0, 5], [1, 0], [5, 3]])
