â€£

DisjointSet:Â https://www.youtube.com/watch?v=ID00PMy0-vE

Cycle in an Undirected Graph:Â https://www.youtube.com/watch?v=n_t0a_8H8VY

Algorithm with Disjoint Set:

- For each vertex, create a set (disjoint set node)
- For each edge, do:
- find_set for both vertices/nodes, and if representatives (or parents) are the same, then there is a cycle
- else, do a union by rank on these two vertices/nodes

```
def hasCycleDisjointSet(edges):
ds = DisjointSet()
vertices = Set([])
for e in edges:
vertices.add(e[0])
vertices.add(e[1])
for v in vertices:
ds.make_set(v)
for e in edges:
if ds.find_set(e[0]) == ds.find_set(e[1]):
return True
ds.union_by_rank(e[0], e[1])
return False
```

Algorithm:

- Maintain a visited set while doing DFS
- For each (not visited) vertex, do dfs, while passing the visited set and current vertex

```
def hasCycle(edges):
visited = Set([])
vertices = Set([*e for e in edges])
adj = {v:{} for v in vertices}
for e in edges:
adj[e[0]][e[1]] = True
adj[e[1]][e[0]] = True
for v in vertices:
if v in visited:
continue
cycle = hasCycleDFSUtil(v, adj, visited, parent = None)
if cycle:
return True
visited.add(v)
return False
def hasCycleDFSUtil(vertex, adj, visited, parent):
visited.add(vertex)
neighbors = adj[vertex]
for n in neighbors:
if n == parent:
continue
if n in visited:
return True
cycle = hasCycleDFSUtil(n, adj, visited, vertex)
if cycle:
return True
return False
```