Union Find Algorithm in Python

[abhaysinghr516]

No description provided.

[alok5050]

Hey, I would like to work on this issue.

[alok5050]

def initialize(n):
global Arr, size
for i in range(n + 1):
Arr[i] = i
size[i] = 1

def find(i):
global Arr, size

while (Arr[i] != i):
    Arr[i] = Arr[Arr[i]] # Skip one level 
    i = Arr[i] # Move to the new level
return i

def _union(xr, yr):
global Arr, size
if (size[xr] < size[yr]): # Make yr parent of xr
Arr[xr] = Arr[yr]
size[yr] += size[xr]
else: # Make xr parent of yr
Arr[yr] = Arr[xr]
size[xr] += size[yr]

def isCycle(adj, V):
global Arr, size

for i in range(V):
    for j in range(len(adj[i])):
        x = find(i) # find root of i 
        y = find(adj[i][j]) # find root of adj[i][j] 

        if (x == y):
            return 1 # If same parent 
        _union(x, y) # Make them connect
return 0

MAX_VERTEX = 101

Arr = [None] * MAX_VERTEX

size = [None] * MAX_VERTEX

V = 3

adj = [[] for i in range(V)]

adj[0].append(1)
adj[0].append(2)
adj[1].append(2)

if (isCycle(adj, V)):
print("Graph contains Cycle.")
else:
print("Graph does not contain Cycle.")

[abhaysinghr516]

Create Pull Request

[nazishkn67]

Hey Abhay, I would like to work on this issue if currently, no one is working on this.