• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Jul 16th, 2019 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # check cycles in graph using union find
2. # weighted tree balancing added
3.
4.
5. from collections import defaultdict
6. class graph:
7.
8.   def __init__(self):
9.
10.     self.graph = defaultdict(list)
11.     self.parents = {}
12.     self.size = {}
13.
14.   def addnode(self, key1, key2, edge=0):
15.     if key2 not in self.graph:
16.       self.graph[key2] = []
17.
18.     self.graph[key1].append(key2)
19.
20.   def findcycle(self):
21.
22.
23.     for key in self.graph:
24.       self.parents[key] = -1
25.       self.size[key] = 1
26.
27.
28.     for vertex in self.graph:
29.       for neighbour in self.graph[vertex]:
30.         x_par = self.getparent(vertex)
31.         y_par = self.getparent(neighbour)
32.         if x_par == y_par:
33.           return True
34.         self.union(x_par, y_par)
35.
36.
37.   def getparent(self, vertex):
38.
39.     while self.parents[vertex] != -1:
40.       vertex = self.parents[vertex]
41.
42.     return vertex
43.
44.
45.   def union(self, vertex, neighbour):
46.
47.     x_par = self.getparent(vertex)
48.     y_par = self.getparent(neighbour)
49.     if self.size[x_par] <= self.size[y_par]:
50.       self.parents[x_par] = y_par
51.       self.size[y_par] += self.size[x_par]
52.     else:
53.       self.parents[y_par] = x_par
54.       self.size[x_par] += self.size[y_par]
55.
56. g = graph()