garrab

'''
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)