[Leetcode] 547. Number of Provinces (Medium)

概述

題目

https://leetcode.com/problems/number-of-provinces/
給定一個 n*n 的 Adjacency Matrix 表示 n 個點組成無向圖之間的連接關係，求共有多少個 group / cluster。

心得

這是一題非常經典的圖題，可以用 DFS 或 Find & Union 來解，DFS 理論上應該是會更直覺一些，但今天 daily 的時候，我第一想法還是用 Find & Union 來解，估計是有模板可以用所以特別靈光一閃

Find & Union

思路

因為題目沒有說不能有環，故在進行 Union 的時候需特注意這部分，故是由大去 merge 小，且方式為透過兩層 for 中，j 一定要大於 i 之方式進行

程式

class Solution(object):
    def findCircleNum(self, isConnected):
        """
        :type isConnected: List[List[int]]
        :rtype: int
        """
        n = len(isConnected)
        
        # 模板應用，p 代表 parent (最根點)
        p = [i for i in range(n)]

        def find(u):
            if p[u] == u:
                return u
            return find(p[u])

        def union(u, v):
            p[find(v)] = p[find(u)]
        
        # 開始 Union，避免環的產生故以大 union 小
        for i in range(n):
            for j in range(i+1, n):
                if isConnected[i][j] == 1:
                    union(i, j)
        
        # 確認 cluster 數量
        cnt = 0
        dic = {}
        for k in p:
            c = find(k)
            if c not in dic:
                dic[c] = 1
                cnt += 1
        return cnt

DFS

思路

遍歷每個點與其連接點，若有連通則加入 cluster；重覆找到所有 cluster

程式

class Solution(object):
    def findCircleNum(self, isConnected):
        """
        :type isConnected: List[List[int]]
        :rtype: int
        """
        n = len(isConnected)

        vis = set()
        def dfs(i):
            q = deque()
            q.append(i)
            vis.add(i)
            while q:
                cur = q.popleft()
                for nxt in range(n):
                    if isConnected[cur][nxt] == 1:
                        if nxt not in vis:
                            vis.add(nxt)
                            q.append(nxt)
        
        # 沒走過的點就 dfs 一次，且計算上一個 cluster
        cnt = 0
        for i in range(n):
            if i not in vis:
                vis.add(i)
                dfs(i)
                cnt += 1

        return cnt

Numpy

思路

此解法為參考 aagrawal 大大的解法，利用線性代數之特性解之：將 Adjacency Matrix 視為 A 矩陣，求出其調和矩陣 L = D-A，其中 A 中的元件 (Components) 數量即是 L 的 nullspace，即 n-rank(L)，此方法計算是 GPU-friendly 且更高效的。

程式

import numpy as np
class Solution(object):
    def findCircleNum(self, isConnected):
        """
        :type isConnected: List[List[int]]
        :rtype: int
        """
        n = len(isConnected)
        # L = D - A
        L = np.diag(np.sum(isConnected, axis=1)) - np.array(isConnected)
        rankL = np.linalg.matrix_rank(L)

        return n - rankL

或者一行解：

import numpy as np
class Solution(object):
    def findCircleNum(self, isConnected):
        """
        :type isConnected: List[List[int]]
        :rtype: int
        """
        return len(isConnected) - np.linalg.matrix_rank(np.diag(np.sum(isConnected, axis=1)) - np.array(isConnected))