Graph
Topological sorting
Template
对于图 G 中的任意一条有向边 (u,v)，u 在排列中都出现在 v 的前面
- 有环则没有拓扑排序
- 拓扑排序不唯一 BFS
Q = deque()
for i in range(1, n+1):
if ind[i] == 0:
d Q.append(i)
while Q:
u = Q.popleft()
topo.append(u)
for v in graph[u]:
ind[v] -= 1
if ind[v] == 0:
Q.append(v)
if len(topo_order) != numCourses:
return[] # 有环
DFS
def dfs(x):
visited[x] = 1
for v in edges[x]:
if visited[v] == 0:
visited[v] = 1
if not dfs(v):
return False
elif visited[v] == 1:
return False
visited[x] = 2
topo.append(x)
for i in range(numCourses):
if valid and not visited[i]:
valid &= dfs(i)
if valid:
topo.reverse()
return topo
return []
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> visited(numCourses, 0);
for (vector<int> prerequisite : prerequisites) {
graph[prerequisite[1]].push_back(prerequisite[0]);
}
for (int i = 0; i < numCourses; ++i)
if (!hasCycle(graph, i, visited))
return false;
return true;
}
private:
bool hasCycle(const vector<vector<int>>& graph, int u, vector<int>& visited) {
visited[u] = 1;
for (const int v : graph[u])
if (visited[v] == 0) {
visited[v] = 1;
if (!hasCycle(graph, v, visited)) return false;
}
else if (visited[v] == 1) return false;
visited[u] = 2;
return true;
}
};
What I have done
207. Course Schedule
210. Course Schedule II
1462. Course Schedule IV
2192. All Ancestors of a Node in a Directed Acyclic Graph
2392. Build a Matrix With Conditions
with graph
684. Redundant Connection
924. Minimize Malware Spread
Has Cycle
Template
two pointer space complexity -> O(1)
while True:
slow = next_index(slow)
fast = next_index(fast)
if nums[fast] * nums[i] <= 0 or nums[next_index(fast)] * nums[i] <= 0:
break
fast = next_index(fast)
if slow == fast:
if slow == next_index(slow):
break
return True
What I have done
457. Circular Array Loop🌟
802. Find Eventual Safe States
1591. Strange Printer II🌟
2115. Find All Possible Recipes from Given Supplies
Union-Find
Template
简易版
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
完整版（按秩）
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [1] * size # height
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
if self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
What I have done
547. Number of Provinces
684. Redundant Connection
685. Redundant Connection II
947. Most Stones Removed with Same Row or
990. Satisfiability of Equality Equations
Shortest Path
Template
Dijkstra
while Q:
u = Q.popleft()
for v in graph[u]:
dist[v] = max(dist[v], dist[u] + time[v])
ind[v] -= 1
if ind[v] == 0:
Q.append(v)
Dijkstra with heap
def Dijkstra(self, graph, src):
dis = [float('inf')] * len(graph)
dis[src] = 0
minHeap = [(dis[src], src)]
while minHeap:
d, u = heapq.heappop(minHeap)
if d > dis[u]:
continue
for v, w in graph[u]:
if d + w < dis[v]:
dis[v] = d + w
heapq.heappush(minHeap, (dis[v], v))
What I have done
797. All Paths From Source to Target
1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
1514. Path with Maximum Probability
1631. Path With Minimum Effort变一下
2050. Parallel Courses III
BFS Variants
What I have done
Tarjan
Template
find cut vertex
dfn = [0] * n
low = [0] * n
ans = []
cur_time = 0
def tarjan(node, parent):
nonlocal cur_time
cur_time += 1
dfn[node] = low[node] = cur_time
for neighbor in graph[node]:
if neighbor == parent:
continue
if not dfn[neighbor]:
tarjan(neighbor, node)
low[node] = min(low[node], low[neighbor])
if low[neighbor] > dfn[node]:
ans.append([node, neighbor])
low[node] = min(low[node], dfn[neighbor])
graph = [[] for _ in range(n)]
for a, b in connections:
graph[a].append(b)
graph[b].append(a)
tarjan(0, -1)
return ans
What I have done
1192. Critical Connections in a Network
MST
Template
Kruskal
def find(self, parent, node):
if parent[node] == node:
return node
parent[node] = self.find(parent, parent[node])
return parent[node]
def union(self, parent, rank, x, y):
root_x = self.find(parent, x)
root_y = self.find(parent, y)
if root_x != root_y:
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
elif rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
parent[root_y] = root_x
rank[root_x] += 1
edges = sorted(edges)
parent = list(range(len(points)))
rank = [0] * len(points)
min_cost = 0
for edge in edges:
distance, u, v = edge
if self.find(parent, u) != self.find(parent, v):
min_cost += distance
self.union(parent, rank, u, v)