图：拓扑排序/Union Find高频题
原创
Union Find
解决动态连通性一类问题
并查集(Union-Find)算法介绍 link
并查集（参考leetcode323题）link
UnionFind Class
class UnionFind:
def __init__(self, n):
self.count = n
self.parent = [i for i in range(n)]
def find(self, idx):
if self.parent[idx] != idx:
self.parent[idx] = self.find(self.parent[idx])
return self.parent[idx]
def union(self, i, j):
i_pos = self.find(i)
j_pos = self.find(j)
if i_pos != j_pos:
self.parent[i_pos] = j_pos
self.count -= 1
def Count(self):
return self.countFind问题：最后idx=parent，为什么不能return idx
200. 岛屿数量
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1Solution
class Solution:
def numIslands(self, grid):
row = len(grid)
col = len(grid[0]) if row else 0
if not row or not col: return 0
dummy_node = row*col
uf = UnionFind(dummy_node+1)
for i in range(row):
for j in range(col):
if grid[i][j] == "0":
uf.union(dummy_node, i*col+j)
if grid[i][j] == "1":
for x,y in [(0,1), (1,0)]:
if i+x<row and j+y<col and grid[i+x][j+y] == '1':
uf.union((i+x)*col+(j+y), (i*col)+j)
return uf.Count()-1323. 无向图中连通分量的数目
给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。
示例 1:
输入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]]
0 3
| |
1 --- 2 4
输出: 2示例 2:
输入: n = 5 和 edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
0 4
| |
1 --- 2 --- 3
输出: 1注意: 你可以假设在 edges 中不会出现重复的边。而且由于所以的边都是无向边，[0, 1] 与 [1, 0] 相同，所以它们不会同时在 edges 中出现。
class UnionFind:
def __init__(self, n):
self.count = n
self.parent = [i for i in range(n)]
def Find(self, p):
if p != self.parent[p]:
self.parent[p] = self.parent[self.parent[p]]
p = self.parent[p]
return self.parent[p]
def Union(self, p, q):
p_root = self.Find(p)
q_root = self.Find(q)
self.parent[p_root] = q_root
self.count -= 1
def IsConnected(self, p, q):
return self.Find(p) == self.Find(q)
def Count(self):
return self.count
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
uf = UnionFind(n)
for i,j in edges:
uf.Union(i,j)
return uf.Count()一遍过的朋友~~
拓扑排序
Workflow:
1. 遍历构造indegree和outdegree
2. 遍历indegree收集indegree为0的节点 -> q
3. while q.pop, 减少当前node的outdegree中节点的indegree，当indegree为零append到q
4. 知道遍历完所有节点，return
207. 课程表
Course Schedule
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: 2, [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.Example 2:
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.Note:
- The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
- You may assume that there are no duplicate edges in the input prerequisites.
Solution
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
indegree = [0 for _ in range(numCourses)]
outdegree = [[] for _ in range(numCourses)]
for nex, pre in prerequisites:
indegree[nex] += 1
outdegree[pre].append(nex)
q = []
for i in range(len(indegree)):
if indegree[i] == 0: q.append(i)
count = 0
while q:
pre = q.pop()
count += 1
for nex in outdegree[pre]:
indegree[nex] -= 1
if not indegree[nex]: q.append(nex)
return count == numCourses之前做的，构造图比较直接，然后拓扑排序
210. 课程表 II
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Input: 2, [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished
course 0. So the correct course order is [0,1] .Example 2:
Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both
courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .Solution
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
indegree = [0 for _ in range(numCourses)]
outdegree = [[] for _ in range(numCourses)]
for nex, pre in prerequisites:
indegree[nex] += 1
outdegree[pre].append(nex)
q = []
for i in range(len(indegree)):
if indegree[i] == 0: q.append(i)
res = []
while q:
pre = q.pop()
res.append(pre)
for nex in outdegree[pre]:
indegree[nex] -= 1
if not indegree[nex]: q.append(nex)
return res if len(res) == numCourses else []269. 火星词典
Alien Dictionary
现有一种使用字母的全新语言，这门语言的字母顺序与英语顺序不同。
假设，您并不知道其中字母之间的先后顺序。但是，会收到词典中获得一个 不为空的 单词列表。因为是从词典中获得的，所以该单词列表内的单词已经 按这门新语言的字母顺序进行了排序。
您需要根据这个输入的列表，还原出此语言中已知的字母顺序。
示例 1：
输入:
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
输出: "wertf"示例 3：
输入:
[
"z",
"x",
"z"
]
输出: ""
解释: 此顺序是非法的，因此返回 ""。注意：
- 你可以默认输入的全部都是小写字母
- 假如，a 的字母排列顺序优先于 b，那么在给定的词典当中 a 定先出现在 b 前面
- 若给定的顺序是不合法的，则返回空字符串即可
- 若存在多种可能的合法字母顺序，请返回其中任意一种顺序即可
Solution
from collections import defaultdict
class Solution(object):
def alienOrder(self, words):
if not words or not words[0]: return ""
indegree = defaultdict(int)
outdegree = defaultdict(set)
res = ""
for i in range(len(words)):
for j in range(i+1, len(words)):
idx = 0
while idx < len(words[i]) and idx < len(words[j]) and words[i][idx] == words[j][idx]:
idx += 1
if idx < len(words[i]) and idx < len(words[j]) and words[j][idx] not in outdegree[words[i][idx]]:
outdegree[words[i][idx]].add(words[j][idx])
indegree[words[j][idx]] += 1
indegree[words[i][idx]] += 0
q = []
for k,v in indegree.items():
if not v:
q.append(k)
res += k
while q:
ch = q.pop()
for next_ch in outdegree[ch]:
indegree[next_ch] -= 1
if not indegree[next_ch]:
q.append(next_ch)
res += next_ch
return res自己写 ，但还有些edge case没过，如["z","z"]
思路：建图，key为前序，value为后继，然后拓扑排序逐个添加入度为零的节点。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。