力扣(LeetCode)之省份数量

题目：

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。

示例：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

方法一：深度优先搜索

我们可以使用递归的方法，设立一个一个visited数组用来记录某个城市是否被访问。如果该城市被访问了，就说明该城市就不需要再寻找了，它已经属于某一个省了。

我们利用递归，一层一层顺藤摸瓜，从叶子节点往根节点，将visited记录进行更改，每搜索完一棵树，就将province计数器加一。其具体代码如下：

# 方法一：深度优先搜索
# 首先找到叶子节点，往上搜索
def fun1(cityConnected):
    citys = len(cityConnected)
    visited = [False]*citys 
    province = 0
    for i in range(citys):
        if not visited[i]:
            # 深度优先
            dfs(i,citys,visited,cityConnected)
            province += 1 
    return province

def dfs(i,citys,visited,cityConnected):
    for j in range(citys):
        if cityConnected[i][j] == 1 and not visited[j]: 
            visited[j] = True 
            dfs(j,citys,visited,cityConnected)

方法二：广度优先搜索

广度优先的思想和深度优先类似，但是查找方法有所不同，深度优先需要依赖栈或者递归进行遍历。广度优先搜索算法则需要队列进行辅助遍历。

广度优先从根节点入手，一层一层往下寻找，直至找到所有的叶子节点，队列也为空了，就说明该树已经遍历完毕，并且将遍历过的城市所对应的visited变量置为True。就能够将province计数器加一。其具体代码如下：

# 方法二：广度优先搜索
def fun2(cityConnected):
    citys = len(cityConnected)
    q = Queue()
    visited = [False]*citys 
    province = 0
    for i in range(citys):
        if not visited[i]:
            q.put(i)
            visited[i] = True

            while not q.empty():
                i = q.get()
                for j in range(citys):
                    if cityConnected[i][j] == 1 and not visited[j]:
                        q.put(j) 
                        visited[j] = True
            province += 1
    return province

方法三：并查集

前两种方法在空间复杂度上是，时间复杂度是，而并查集使用空间换时间。此算法中我们需要两个数组变量。一个为head，长度为citys，用于保存每一个城市所属的根节点值。另一个为level，长度为citys，用于保存所属根节点的深度。

我们通过两层for循环遍历矩阵，寻找相邻的两个城市，如果两个城市有链接就可以将两个城市进行合并，合并的具体操作如代码所示。最后我们遍历完所有的相邻城市，就能够总结出每一个城市所属省份，最终遍历head数组我们就能够得出省份个数。其具体代码如下：

# 方法三：并查集
# 把拥有相同子节点的树能够合并到一起
# 我们需要维护，每一棵树的深度level，根节点head 
# 如果数组下标和根节点值相同，说明这是一颗独立的数
# 合并操作：小树加到大树下面，大树的深度不变。
# 如果两棵树深度相同，被加入的树的深度加一
def fun3(cityConnected):
    citys = len(cityConnected)
    head = [c for c in range(citys)] # 初始化，每个节点认为自己是一个省
    level = [1]*citys # 每个省的深度为1

    for i in range(citys): # 遍历每一个城市，寻找相邻的城市
        for j in range(i+1, citys):
            if cityConnected[i][j] == 1: # 城市i与j是相邻的，所以需要合并
                merge(i,j,head, level)  
    print(head)
    print(level)
    return len(list(set(head)))

def merge(x,y,head,level):
    i = find(x, head) # 寻找根节点，寻找所属省份
    j = find(y, head) # 寻找根节点，寻找所属省份

    if i == j: return # 如果两者属于同一个省份则不需要合并
    # 小树并入大树，根节点变为大树，level升高
    if level[i] < level[j]: # j树更高
        head[i] = j 
        level[i] = level[j]
    elif level[i] > level[j]: # i树更高
        head[j] = head[i]
        level[j] = level[i]
    else: # 两棵树一样高
        head[j] = head[i] # 把j树加到i树上面
        level[i] += 1 
        level[j] += 1

def find(x, head):
    if head[x] == x: return x 
    head[x] = find(head[x], head)
    return head[x]

全部代码：

from queue import Queue 

# 省份的数量, 1表示相连接，0表示不连接，丝毫不连接的节点组成一个省
arr1 = [[1,1,0],[1,1,0],[0,0,1]] # 2
arr2 = [[1,0,0],[0,1,0],[0,0,1]] # 3

# 方法一：深度优先搜索
# 首先找到叶子节点，往上搜索
def fun1(cityConnected):
    citys = len(cityConnected)
    visited = [False]*citys 
    province = 0
    for i in range(citys):
        if not visited[i]:
            # 深度优先
            dfs(i,citys,visited,cityConnected)
            province += 1 
    return province

def dfs(i,citys,visited,cityConnected):
    for j in range(citys):
        if cityConnected[i][j] == 1 and not visited[j]: 
            visited[j] = True 
            dfs(j,citys,visited,cityConnected)

# 方法二：广度优先搜索
def fun2(cityConnected):
    citys = len(cityConnected)
    q = Queue()
    visited = [False]*citys 
    province = 0
    for i in range(citys):
        if not visited[i]:
            q.put(i)
            visited[i] = True

            while not q.empty():
                i = q.get()
                for j in range(citys):
                    if cityConnected[i][j] == 1 and not visited[j]:
                        q.put(j) 
                        visited[j] = True
            province += 1
    return province


# 方法三：并查集
# 把拥有相同子节点的树能够合并到一起
# 我们需要维护，每一棵树的深度level，根节点head 
# 如果数组下标和根节点值相同，说明这是一颗独立的数
# 合并操作：小树加到大树下面，大树的深度不变。
# 如果两棵树深度相同，被加入的树的深度加一
def fun3(cityConnected):
    citys = len(cityConnected)
    head = [c for c in range(citys)] # 初始化，每个节点认为自己是一个省
    level = [1]*citys # 每个省的深度为1

    for i in range(citys): # 遍历每一个城市，寻找相邻的城市
        for j in range(i+1, citys):
            if cityConnected[i][j] == 1: # 城市i与j是相邻的，所以需要合并
                merge(i,j,head, level)  
    print(head)
    print(level)
    return len(list(set(head)))

def merge(x,y,head,level):
    i = find(x, head) # 寻找根节点，寻找所属省份
    j = find(y, head) # 寻找根节点，寻找所属省份

    if i == j: return # 如果两者属于同一个省份则不需要合并
    # 小树并入大树，根节点变为大树，level升高
    if level[i] < level[j]: # j树更高
        head[i] = j 
        level[i] = level[j]
    elif level[i] > level[j]: # i树更高
        head[j] = head[i]
        level[j] = level[i]
    else: # 两棵树一样高
        head[j] = head[i] # 把j树加到i树上面
        level[i] += 1 
        level[j] += 1

def find(x, head):
    if head[x] == x: return x 
    head[x] = find(head[x], head)
    return head[x]

print(fun3(arr1))