Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- '''
- Complexity: O(m log(n))
- m is the number of uf operations while n is the number of objects
- '''
- from collections import defaultdict
- from itertools import combinations
- def f(x, y):
- c1 = ((x == "Berlin") and (y == "Hamburg")) or ((y=="Hamburg") and (x=="Berlin"))
- c2 = ((x == "Hamburg") and (y == "Bremen")) or ((y=="Bremen") and (x=="Hamburg"))
- return c1 or c2
- def union(data, i, j):
- pi, pj = find(data, i), find(data, j)
- if pi != pj:
- data[pi] = pj
- def find(data, i):
- if data[i] != i:
- data[i] = find(data, data[i])
- return data[i]
- '''
- ## Step 1
- Berlin: Berlin
- Hamburg: Hamburg
- Munich: Munich
- Bremen: Bremen
- ## Step 2 = f(Berlin, Hamburg) = True
- Berlin: Berlin
- Hamburg: Berlin
- Munich: Munich
- Bremen: Bremen
- ...etc
- '''
- data = defaultdict(str)
- cities = ["Berlin", "Hamburg", "Munich", "Bremen"]
- # Initially all cities are in a separate group
- for c in cities:
- data[c] = c
- # combinations -> O(N^2) where N is number of cities
- # Proof:
- # combinations formula => nCr => (n! / (r!(n-r)!)) where r = 2
- # n(n-1) / 2 = O(n^2)
- for i,j in combinations(cities,2):
- if f(i,j):
- union(data, i, j)
- print (data)
- groups = defaultdict(list)
- for k in data:
- groups[data[k]].append(k)
- print (groups)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement