Connect

查询两个元素是否在同一个集合内。

LintCode 589. Connecting Graph

Given n nodes in a graph labeled from 1 to n. There is no edges in the graph at beginning.

You need to support the following method:

1. connect(a, b), add an edge to connect node a and node b`.
2. query(a, b), check if two nodes are connected

class ConnectingGraph:
    def __init__(self, n):
        self.root = range(n+1)

    # Find the Root of node x
    def find(self, x):
        root = self.root # tip1 : root在类里面要加上"self."
        if root[x] == x:
            return x
        root[x] = self.find(root[x])
        return root[x]

    def union(self, x, y):
        root = self.root
        rootx = self.find(x) # tip2 : root[x] vs find(x)
        rooty = self.find(y)
        if rootx != rooty:
            root[rootx] = rooty

    def connect(self, a, b):
        self.union(a, b)

    def query(self, a, b):
        return self.find(a) == self.find(b)

130. Surrounded Regions

• 解法1 DFS

从边缘的'O'出发，通过DFS，所有能够遍历的'O'都可以暂时被标记为'#'，那么剩下未能被标记的'O'说明被surrounded，需要在遍历结束之后全部转为'X'

• 解法2 Union Find

将与边缘相连通的'O'全部union到一个dummy node（也可以用hasEdge[]来存储，不过内存占用更多, 最终将没有和这个dummy node是一个component的'O'点全部标记为'X

class UnionFind(object):
    def __init__(self, n):
        self.root = range(n)

    def find(self, x):
        root = self.root
        if root[x] == x:
            return x
        root[x] = self.find(root[x])
        return root[x]

    def union(self, x, y):
        root = self.root
        rootx = self.find(x)
        rooty = self.find(y)
        if rootx != rooty:
            # tip : 为了总是以dummy node(total)为父节点
            root[min(rootx, rooty)] = max(rootx, rooty)

class Solution(object):
    def solve(self, board):
        if not board:
            return
        m, n = len(board), len(board[0])
        total = m*n
        uf = UnionFind(total+1)
        grid = board
        for i in xrange(m):
            for j in xrange(n):
                if grid[i][j] == 'X':
                    continue
                # Connect to "total" root
                if i == 0 or j == 0 or i == m-1 or j == n-1:
                    uf.union(total, i*n+j)
                else:
                    d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
                    for k in xrange(4):
                        ni, nj = i + d[k][0], j + d[k][1]
                        if grid[ni][nj] == 'O':
                            uf.union(ni*n + nj, i*n + j)
        for i in xrange(m):
            for j in xrange(n):
                if grid[i][j] == 'X':
                    continue
                if uf.find(i*n + j) != total:
                    grid[i][j] = 'X'

737. Sentence Similarity II

典型的Union Find 应用题，两个单词是不是similarity其实就是两个单词在不在同一个集合内(connected 操作)！

class UnionFind(object):
    def __init__(self, n):
        self.root = range(n)

    def find(self, x):
        root = self.root
        if root[x] == x:
            return x
        root[x] = self.find(root[x])
        return root[x]

    def union(self, x, y):
        self.root[self.find(x)] = self.find(y)

class Solution(object):
    def areSentencesSimilarTwo(self, words1, words2, pairs):
        m, n = len(words1), len(words2)
        if m != n: return False

        # 建立words到index的映射关系！UnionFind 只支持数字的index！
        uf = UnionFind(len(pairs)*2)
        cnt = 0
        pdic = {}
        for w1, w2 in pairs:
            if w1 not in pdic:
                pdic[w1] = cnt
                cnt += 1
            if w2 not in pdic:
                pdic[w2] = cnt
                cnt += 1
            uf.union(pdic[w1], pdic[w2])

        for w1, w2 in zip(words1, words2):
            if w1 == w2:
                continue
            if w1 not in pdic or w2 not in pdic:
                return False
            if uf.find(pdic[w1]) != uf.find(pdic[w2]):
                return False
        return True