Cycle detection with DFS coloring, bipartite check with BFS, and Kruskal MST with Union-Find.
Advanced Graph Algorithms
# Detect cycle in directed graph (DFS)
def has_cycle(graph):
WHITE,GRAY,BLACK = 0,1,2
color = {n:WHITE for n in graph}
def dfs(node):
color[node] = GRAY # in current DFS path
for nb in graph[node]:
if color[nb]==GRAY: return True # back edge = cycle
if color[nb]==WHITE and dfs(nb): return True
color[node] = BLACK # done
return False
return any(dfs(n) for n in graph if color[n]==WHITE)
# Bipartite check (2-coloring)
def is_bipartite(graph):
color = {}
for start in graph:
if start in color: continue
queue = deque([start])
color[start] = 0
while queue:
node = queue.popleft()
for nb in graph[node]:
if nb not in color:
color[nb] = 1-color[node]
queue.append(nb)
elif color[nb]==color[node]:
return False
return True
# Minimum Spanning Tree (Kruskal's) O(E log E)
def kruskal(n, edges):
uf = UnionFind(n)
edges.sort(key=lambda e: e[2])
mst_cost = 0
for u,v,w in edges:
if uf.union(u,v): mst_cost += w
return mst_cost