preface
在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，称该图为非连通图，则其中的极大连通子图称为连通分量，这里所谓的极大是指子图中包含的顶点个数极大。
在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大强连通子图称为强连通分量。
DAG （Directed acyclic graph），有向无环图。
332. 重新安排行程⭐
给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
说明:
- 如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前
- 所有的机场都用三个大写字母表示（机场代码）。
- 假定所有机票至少存在一种合理的行程。
#map硬套不行啊，会在图里死循环。
#什么是欧拉路径？欧拉路径就是一条能够不重不漏地经过图上的**每一条边**的路径，
#即小学奥数中的一笔画问题。而若这条路径的起点和终点相同，则将这条路径称为欧拉回路。
#如何判断一个图是否有欧拉路径呢？显然，与一笔画问题相同，一个图有欧拉路径需要以下几个条件：
# 1. 首先，这是一个连通图
# 2. 若是无向图，则这个图的度数为奇数的点的个数必须是0或2；
# 若是有向图，则要么所有点的入度和出度相等，要么有且只有两个点的入度分别比出度大1和少1
#具有欧拉回路的无向图称为欧拉图。
#具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图。
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
d = defaultdict(list)
for depart, arrive in tickets:
d[depart].append(arrive)
def dfs(cur):
while d[cur]:
tmp = heappop(d[cur])
dfs(tmp)
stack.append(cur)
# 因为要字典序返回最小的行程，所以使用堆的 heappop
# 如果没有这个要求，随便 pop 都是可以的
for key in d:
heapify(d[key])
stack = []
dfs("JFK")
return stack[::-1]
- 由于题目中说必然存在一条有效路径(至少是半欧拉图)，所以算法不需要回溯（既加入到结果集里的元素不需要删除）
- 整个图最多存在一个死胡同(出度和入度相差1），且这个死胡同一定是最后一个访问到的，否则无法完成一笔画。
- DFS的调用其实是一个拆边的过程（既每次调用删除一条边），一定是递归到这个死胡同（无边可拆）后递归函数开始返回。所以死胡同是第一个加入栈中的元素。
- 最后逆序的输出即可。
5932. 合法重新排列数对
class Solution:
def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
d = defaultdict(list)
out = Counter()
for u, v in pairs:
d[u].append(v)
out[u] += 1
out[v] -= 1
res = []
def dfs(cur, pre = None):
while d[cur]:
tmp = d[cur].pop()
dfs(tmp, cur)
if pre is not None:
res.append([pre, cur])
for begin, f in out.items():
if f == 1:
break
dfs(begin)
return res[::-1]
133.克隆图（8.12)
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
class Solution(object):
def __init__(self):
self.visited={} #新node字典
def cloneGraph(self, node):
if not node: return node
if node in self.visited:
return self.visited[node]
clone_node=Node(node.val,[])
self.visited[node]=clone_node
clone_node.neighbors=[self.cloneGraph(n) for n in node.neighbors]
return clone_node
# 对于一张图而言，它的深拷贝即构建一张与原图结构，值均一样的图，但是其中的节点不再是原来图节点的引用.
# 或者用copy.deepcopy
207. 课程表
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
vis = set()
indegree = [0]*numCourses
d = defaultdict(list)
for a, b in prerequisites:
d[a].append(b)
indegree[b] += 1
q = deque([i for i in range(numCourses) if indegree[i]==0])
while q:
i = q.popleft()
vis.add(i)
for j in d[i]:
indegree[j] -= 1 #入度变更
if indegree[j] == 0:
q.append(j)
return len(vis) == numCourses
5909. 并行课程 III ⭐
你可以并行学习课程，先修课都要修，返回完成所有课程所需要的最少时间。
# 利用入度为 0 的队列来实现遍历图
class Solution:
def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
d = defaultdict(list)
c=[0]*n
for x,y in relations:
d[x-1].append(y-1)
c[y-1] += 1
q = deque()
t = [0]*n
ans = max(time)
for i in range(n):
t[i] = time[i]
if c[i] == 0: #入度为0
q.append(i)
while len(q):
i = q.popleft()
ans=max(ans,t[i])
for j in d[i]:
c[j] -= 1
t[j] = max(t[j], t[i]+time[j])
if c[j] == 0:
q.append(j)
return ans
