Detect Cycle in an Undirected Graph

In [9]:

import sys
sys.path.append("/home/swyoo/algorithm/")
from utils.verbose import visualize_ds

Detect Cycles in an Undirected Graph

In [11]:

def solution(graph):

    par, rnk = {}, {}

    def find(x):
        if x not in par:
            par[x] = x
            rnk[x] = 0
        if x != par[x]:
            par[x] = find(par[x])
        return par[x]

    def union(x, y):
        x, y = find(x), find(y)
        if x == y: return
        if rnk[x] > rnk[y]:
            x, y = y, x
        par[x] = y
        if rnk[x] == rnk[y]:
            rnk[y] += 1

    # enumerate all edges
    for u, vlist in enumerate(graph):
        for v in vlist:
            x, y = find(u), find(v)
            if x == y:
                print("detect cycle: {} with {}".format(u, v))
                return par
            else:
                union(x, y)
    return par

In [12]:

graph = [[1,2,3],[0,2],[0,1],[0,4],[3]]
visualize_ds(solution(graph))

detect cycle: 1 with 0