Jianbo Dai's

lc547.省份数量

 
  • Mar 13, 2021

题目链接

最近在复习并查集，所以做了下这个题，这个题用bfs或dfs也是能做的，不过这里只讲一讲quick-union方法。显然，对于各个城市，我们用union函数将有直接或者间接联系的两个城市连接起来，前面这部分我倒是写对了，只是在计算省份数量多时候没有彻底搞清楚，要知道UF这个字典里存的是其父节点而非最祖先的根节点，因此在计算连通分量的时候，应该计算对于所有UF里的键值对键和值想等的情况。这个算法的时间复杂度是O（N^2logN），空间复杂度是O（N）。注意目前并没有使用按秩排序，而2是在union函数中使用了按秩排序的。

python:

class Solution:
    def findCircleNum1(self, isConnected: List[List[int]]) -> int:
        
        uf = dict()
        def find(x):
            uf.setdefault(x, x)
            if uf[x] != x:
                uf[x] = find(uf[x])
            return uf[x]

        def union(x, y):
            uf[find(x)] = find(y)

        if not isConnected:
            return 0
        prov = len(isConnected)

        for i in range(prov):
            for j in range(i, prov):
                if isConnected[i][j] == 1:
                    union(i, j)
        
        print(uf)
        res = 0
        for k, v in uf.items():
            res += 1 if k == v else 0

        return res
		
    def findCircleNum2(self, isConnected: List[List[int]]) -> int:
        
        rank = dict()
        uf = dict()
        def find(x):
            uf.setdefault(x, x)
            if uf[x] != x:
                uf[x] = find(uf[x])
            return uf[x]

        def union(x, y):
            x_par, y_par = find(x), find(y)
            if x_par == y_par:
                return
            if rank.setdefault(x, 1) < rank.setdefault(y_par, 1):
                uf[x_par] = y_par
                rank[y_par] += rank[x_par]
            else:
                uf[y_par] = x_par
                rank[x_par] += rank[y_par]

        if not isConnected:
            return 0
        prov = len(isConnected)

        for i in range(prov):
            for j in range(i, prov):
                if isConnected[i][j] == 1:
                    union(i, j)
        
        print(uf)
        res = 0
        for k, v in uf.items():
            res += 1 if k == v else 0

        return res
Search