Problem:


Score : 400 points

Problem Statement

There are N cities. There are also K roads and L railways, extending between the cities.
The i-th road bidirectionally connects the p_i-th and q_i-th cities, and the i-th railway bidirectionally connects the r_i-th and s_i-th cities.
No two roads connect the same pair of cities. Similarly, no two railways connect the same pair of cities.

We will say city A and B are connected by roads if city B is reachable from city A by traversing some number of roads. Here, any city is considered to be connected to itself by roads.
We will also define connectivity by railways similarly.

For each city, find the number of the cities connected to that city by both roads and railways.

Constraints

2 ≦ N ≦ 2*10^5

1 ≦ K, L≦ 10^5

1 ≦ p_i, q_i, r_i, s_i ≦ N

p_i < q_i

r_i < s_i

When i ≠ j, (p_i, q_i) ≠ (p_j, q_j)

When i ≠ j, (r_i, s_i) ≠ (r_j, s_j)

Input

The input is given from Standard Input in the following format:

N K L
p_1 q_1
:
p_K q_K
r_1 s_1
:
r_L s_L

Output

Print N integers. The i-th of them should represent the number of the cities connected to the i-th city by both roads and railways.

Sample Input 1

4 3 1
1 2
2 3
3 4
2 3

Sample Output 1

1 2 2 1

All the four cities are connected to each other by roads.

By railways, only the second and third cities are connected. Thus, the answers for the cities are 1, 2, 2 and 1, respectively.

Sample Input 2

4 2 2
1 2
2 3
1 4
2 3

Sample Output 2

1 2 2 1

Sample Input 3

7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7

Sample Output 3

1 1 2 1 2 2 2



Sample input:
4 3 1
1 2
2 3
3 4
2 3


Sample output:
1 2 2 1

Submission status: Accepted

Solution code:
from collections import defaultdict

class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    def find(self,x):#親を探す
        if self.par[x] ==x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self,x,y):#x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)

N,K,L = map(int,input().split())
load = Unionfindtree(N)
train = Unionfindtree(N)
for i in range(K):
    a,b = map(int,input().split())
    load.union(a-1,b-1)
for i in range(L):
    a,b = map(int,input().split())
    train.union(a-1,b-1)

ar = [(load.find(i),train.find(i)) for i in range(N)]

dd = defaultdict(int)
for s in ar:
    dd[s] += 1
ans =[]
for i in range(N):
    ans.append(dd[ar[i]])
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000)

n, k, l = map(int, input().split())
a = [list() for _ in range(n)]
b = [list() for _ in range(n)]
for _ in range(k):
    p, q = [int(x) - 1 for x in input().split()]
    a[p].append(q)
    a[q].append(p)
for _ in range(l):
    r, s = [int(x) - 1 for x in input().split()]
    b[r].append(s)
    b[s].append(r)

def g(a, b, i, k):
    b[i] = k
    for e in a[i]:
        if b[e] is not None: continue
        g(a, b, e, k)

def f(a, b):
    k = 0
    for i in range(n):
        if b[i] is not None: continue
        g(a, b, i, k)
        k += 1

c = [None] * n
f(a, c)
d = [None] * n
f(b, d)
e = {}
for i in range(n):
    k = (c[i], d[i])
    e[k] = e.get(k, 0) + 1

print(' '.join([str(e[(c[i], d[i])]) for i in range(n)]))

Submission status: Accepted

Solution code:
from collections import Counter
n,k,l = (int(i) for i in input().split())
rpar,tpar,x = [i for i in range(n+1)],[i for i in range(n+1)],[]
def root(x,par):
	if par[x]!=x: par[x] = root(par[x],par)
	return par[x]
def unite(x,y,par):
	x2,y2 = root(x,par),root(y,par)
	if x2==y2: return
	par[x2] = y2
r = [[int(i) for i in input().split()] for i in range(k)]
t = [[int(i) for i in input().split()] for i in range(l)]
for i,j in r: unite(i,j,rpar)
for i,j in t: unite(i,j,tpar)
for i in range(1,n+1): x.append((root(i,rpar),root(i,tpar)))
y = Counter(x)
for i in x: print(y[i],end=" ")

Submission status: Accepted

Solution code:
from collections import defaultdict
N,K,L = map(int,input().split())

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def check(self, x, y):
        return self.find(x) == self.find(y)

P,Q = UnionFind(N),UnionFind(N)
for _ in range(K):
    x,y = map(int,input().split())
    P.unite(x,y)
for _ in range(L):
    x,y = map(int,input().split())
    Q.unite(x,y)

D = defaultdict(int)
for i in range(1,N+1):
    D[P.find(i),Q.find(i)] += 1

print(" ".join(map(str,list(D[P.par[i],Q.par[i]] for i in range(1,N+1)))))

Submission status: Accepted

Solution code:
from collections import defaultdict

N,K,L=map(int,input().split())

class UnionFind(object):
  def __init__(self,n):
    self.table=[-1]*n
 
  def find(self,x):
    parent=self.table[x]
    if parent<0:
      return x
    else:
      root=self.find(parent)
      self.table[x]=root
      return root
 
  def union(self,a,b):
    root1=self.find(a)
    root2=self.find(b)
    if root1 != root2:
      if self.table[root1] != self.table[root2]:
        if self.table[root1] < self.table[root2]:
          self.table[root2]=root1
        else:
          self.table[root1]=root2
      else:
        self.table[root1]+=(-1)
        self.table[root2]=root1
      
ufK=UnionFind(N)
for i in range(K):
  p,q=map(int,input().split())
  ufK.union(p-1,q-1)

ufL=UnionFind(N)
for i in range(L):
  p,q=map(int,input().split())
  ufL.union(p-1,q-1)

KL=defaultdict(int)
ans=[]
for i in range(N):
  a=ufK.find(i)
  b=ufL.find(i)
  KL[(a,b)]+=1
for i in range(N):
  a=ufK.find(i)
  b=ufL.find(i)
  ans.append(KL[(a,b)])
  
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind(object):

    def __init__(self, n):
        # 親のnodeを表す
        self.par = [i for i in range(n)]

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            # 経路圧縮
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        self.par[x] = y


class UnionFindRank(UnionFind):

    def __init__(self, n):
        UnionFind.__init__(self, n)

        self.rank = [0 for _ in range(n)]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

def _abc049_d():
    """連結"""

    N, K, L = list(map(int, input().split(' ')))
    ur = UnionFindRank(N)
    for _ in range(K):
        p, q = list(map(int, input().split(' ')))
        p -= 1
        q -= 1
        ur.union(p, q)

    ut = UnionFindRank(N)
    for _ in range(L):
        r, s = list(map(int, input().split(' ')))
        r -= 1
        s -= 1
        ut.union(r, s)

    def _id(r, t):
        return r * 1e8 + t

    from collections import defaultdict
    d = defaultdict(int)

    ids = []
    for i in range(N):
        __id = _id(ur.root(i), ut.root(i))
        d[__id] += 1
        ids.append(__id)

    for i in range(N):
        print(d[ids[i]], end=' ')

_abc049_d()

Submission status: Accepted

Solution code:
class UnionFind(object):

    def __init__(self, n):
        # 親のnodeを表す
        self.par = [i for i in range(n)]

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            # 経路圧縮
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        self.par[x] = y


class UnionFindRank(UnionFind):

    def __init__(self, n):
        UnionFind.__init__(self, n)

        self.rank = [0 for _ in range(n)]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

def _abc049_d():
    """連結"""

    N, K, L = list(map(int, input().split(' ')))
    ur = UnionFindRank(N)
    for _ in range(K):
        p, q = list(map(int, input().split(' ')))
        p -= 1
        q -= 1
        ur.union(p, q)

    ut = UnionFindRank(N)
    for _ in range(L):
        r, s = list(map(int, input().split(' ')))
        r -= 1
        s -= 1
        ut.union(r, s)

    def _id(r, t):
        return r * 1e8 + t

    from collections import defaultdict
    d = defaultdict(int)

    for i in range(N):
        d[_id(ur.root(i), ut.root(i))] += 1

    for i in range(N):
        print(d[_id(ur.root(i), ut.root(i))], end=' ')

_abc049_d()

Submission status: Accepted

Solution code:
class uf_tree:
    def __init__(self, n):
        self.sizes = [0] * n
        self.par = range(n)

    def find(self, x):
        if x == self.par[x]:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.par[y] = x
        self.sizes[x] += self.sizes[y]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return self.sizes[find(x)]


N, K, L = map(int, raw_input().split())

uf_1 = uf_tree(N+1)
uf_2 = uf_tree(N+1)

for i in range(K):
    p, q = map(int, raw_input().split())
    uf_1.unite(p, q)

for i in range(L):
    r, s = map(int, raw_input().split())
    uf_2.unite(r, s);

dic = {}

for i in range(1, N+1):
    key = (uf_1.find(i), uf_2.find(i))
    dic[key] = dic.get(key, 0) + 1

for i in range(1, N+1):
    print dic[(uf_1.find(i), uf_2.find(i))],

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter

N,K,L=map(int, raw_input().split())

nl=[ [] for i in range(N+1) ]

for i in range(K):
	p,q=map(int, raw_input().split())
	nl[p].append(q)
	nl[q].append(p)

nl2=[ [] for i in range(N+1) ]

for i in range(L):
	p,q=map(int, raw_input().split())
	nl2[p].append(q)
	nl2[q].append(p)


v1=[ None for i in range(N+1) ]
v2=[ None for i in range(N+1) ]


def bfs(start,nl,V,l):
	q = deque([]) 
	V[start]=1
	l[start]=start
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in nl[v]:
			if V[i] is None:
				V[i]=1
				q.append(i)
				l[i]=start
			
	return V

l1=[ "" for i in range(N+1) ]
l2=[ "" for i in range(N+1) ]


for i in range(1,N+1):
	if v1[i] is None:
		bfs(i,nl,v1,l1)

for i in range(1,N+1):
	if v2[i] is None:
		bfs(i,nl2,v2,l2)


c=[]
for idx,i in enumerate( zip(l1,l2) ):
	x=i[0]; y=i[1]
	if idx==0: continue
	c.append( (x,y) )


C=Counter(c)

for idx,i in enumerate( zip(l1,l2) ):
	x=i[0]; y=i[1]
	if idx==0: continue
	print C[(x,y)],

Submission status: Accepted

Solution code:
from collections import Counter
N, K, L = map(int, input().split())
u1, u2 = list(range(N+1)), list(range(N+1))

def root(u, r):
    if u[r] == r:
        return r
    u[r] = root(u, u[r])
    return u[r]

def update(u, r, n):
    rr = root(u, r)
    nr = root(u, n)
    if rr > nr:
        rr, nr = nr, rr
    u[nr] = rr

for i in range(K):
    p, q = map(int, input().split())
    update(u1, p, q)

for i in range(L):
    r, s = map(int, input().split())
    update(u2, r, s)

rs = [(root(u1, i), root(u2, i)) for i in range(1, N+1)]
c = Counter(rs)
 
print(' '.join(map(str, [c[r] for r in rs])))

Submission status: Accepted

Solution code:
def d_Connectivity(N, K, L, R, T):  # 都市数、道路数、鉄道数、都市の道路/鉄道による結び
    class UnionFind:
        def __init__(self, N):
            self.p = list(range(N))  # 初期状態ではi番の頂点の根(parent)はi番である
            self.rank = [0] * N  # 初期状態ではどの頂点もランクが0とする(何もつながっていない)
            self.size = [1] * N  # 初期状態ではどの頂点も連結成分の大きさは1

        def find(self, x):
            # 頂点xが属する連結成分の代表(根の番号)を求める
            if self.p[x] != x:
                # 頂点xの根は他の頂点だった
                self.p[x] = self.find(self.p[x])  # 経路圧縮
            return self.p[x]

        def is_same(self, x, y):
            # 頂点x,yは同じ連結成分に属するか？
            return self.find(x) == self.find(y)

        def union(self, x, y):
            # x,yを同じ連結成分に属させる
            u = self.find(x)
            v = self.find(y)
            if u == v:
                # 同じ連結成分に既に属していた
                return
            if self.rank[u] < self.rank[v]:
                self.p[u] = v  # ランクの大きな方につなげる
                self.size[v] += self.size[u]  # つながっている要素数だけ足す
                self.size[u] = 0  # ランクが小さかった連結成分は「解散」
            else:
                # 上と同様にやる
                self.p[v] = u
                self.size[u] += self.size[v]
                self.size[v] = 0
                if self.rank[u] == self.rank[v]:
                    # 根の分だけ1個「ずれる」
                    self.rank[u] += 1

        def get_size(self, x):
            # 頂点xが属する連結成分の大きさ
            return self.size[self.find(x)]

        def show(self):
            return self.p

    road = UnionFind(N)  # 道路による町のつながり
    train = UnionFind(N)  # 鉄道による町のつながり
    for p, q in R:
        road.union(p - 1, q - 1)
    for r, s in T:
        train.union(r - 1, s - 1)

    from collections import defaultdict
    d = defaultdict(int)
    for i in range(N):
        d[road.find(i), train.find(i)] += 1  # 道路も鉄道もつながっている
    ans = (d[road.find(i), train.find(i)] for i in range(N))
    return ' '.join(str(i) for i in ans)

N,K,L = [int(i) for i in input().split()]
R = [[int(i) for i in input().split()] for j in range(K)]
T = [[int(i) for i in input().split()] for j in range(L)]
print(d_Connectivity(N, K, L, R, T))

Submission status: Accepted

Solution code:
from collections import Counter
N,K,L = map(int,input().split())

p_road = [i for i in range(N)]
p_rail = [i for i in range(N)]

def root(a,par):
    if a == par[a]: return a
    par[a] = root(par[a],par)
    return par[a]

def unite(a,b,par):
    ra = root(a,par)
    rb = root(b,par)
    if ra == rb: return
    par[ra] = rb

for i in range(K):
    a,b = map(lambda x:int(x)-1, input().split())
    unite(a,b,p_road)

for i in range(L):
    a,b = map(lambda x:int(x)-1, input().split())
    unite(a,b,p_rail)

road_ids = []
rail_ids = []
for i in range(N):
    road_ids.append(root(i,p_road))
    rail_ids.append(root(i,p_rail))

ctr = Counter()
for a,b in zip(road_ids, rail_ids):
    ctr.update([(a,b)])

print(' '.join(list(map(str, [ctr[(road_ids[i], rail_ids[i])] for i in range(N)]))))

Submission status: Accepted

Solution code:
N, K, L = map(int, input().split())
u1 = [i for i in range(N)]
u2 = [i for i in range(N)]

def root(u, n):
    if u[n] == n:
        return n
    else:
        t = root(u, u[n])
        u[n] = t
        return t

def update(u, r, n):
    u[root(u, n)] = root(u, r)

for i in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    update(u1, p, q)

for i in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    update(u2, r, s)

p = [(root(u1, i), root(u2, i)) for i in range(N)]
ans = {}
for x in p:
    if x not in ans:
        ans[x] = 1
    else:
        ans[x] += 1
print(' '.join(map(str, [ans[x] for x in p])))

Submission status: Accepted

Solution code:
n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[{i} for i in range(n)]
rail=[{i} for i in range(n)]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].add(q)
    road[q].add(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].add(s)
    rail[s].add(r)
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(road[tmp])
        road[i].update(road[tmp])
    for j in road[i]:
        road[j]=road[i]
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(rail[tmp])
        rail[i].update(rail[tmp])
    for j in rail[i]:
        rail[j]=rail[i]
ans=[0]*n
for i in range(n):
    if ans[i]!=0:
        continue
    sumset=road[i]&rail[i]
    for j in sumset:
        ans[j]=str(len(sumset))
print(" ".join(ans))

Submission status: Accepted

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 5 + 1)


class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))

    def is_same_set(self, x: int, y: int) -> bool:
        return self.find_root(x) == self.find_root(y)

    def union_set(self, x: int, y: int):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return

        self.parent[x] = y

    def find_root(self, x: int):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find_root(self.parent[x])
            return self.parent[x]


def main():
    N, K, L = map(int, input().split())
    uf1 = UnionFind(N)
    for _ in range(K):
        p, q = map(int, input().split())
        p -= 1
        q -= 1
        uf1.union_set(p, q)

    uf2 = UnionFind(N)
    for _ in range(L):
        r, s = map(int, input().split())
        r -= 1
        s -= 1
        uf2.union_set(r, s)

    groups = [(uf1.find_root(i), uf2.find_root(i)) for i in range(N)]
    c = Counter(groups)

    print(*(c[g] for g in groups))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

class UnionFind:
    def __init__(self, size):
        self.size = size
        self.parents = list(range(size))

    def union(self, x, y):
        r = self.find(x)
        self.parents[r] = self.find(y)

    def find(self, x):
        path = [x]
        v = x
        while self.parents[v]!=v:
            v = self.parents[v]
            path.append(v)
        for p in path:
            self.parents[p] = v
        return v

if __name__=='__main__':
    n, k, l = map(int, input().split())

    road = UnionFind(n)
    for p, q in (map(int, input().split()) for _ in range(k)):
        road.union(p-1, q-1)

    railway = UnionFind(n)
    for r, s in (map(int, input().split()) for _ in range(l)):
        railway.union(r-1, s-1)

    groups = [str(road.find(i))+"&"+str(railway.find(i)) for i in range(n)]
    ctr = Counter(groups)

    print(*(ctr[g] for g in groups))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
INF=10**10
from collections import deque

def dfs(N,graph):
    arr=[-1 for _ in range(N)]
    queue=deque()
    temp=0
    for i in range(N):
        if arr[i]!=-1:
            continue
        arr[i]=temp
        for i in graph[i]:
            queue.append(i)
        while(queue):
            to=queue.pop()
            arr[to]=temp
            for i in graph[to]:
                if arr[i]==-1:
                    queue.append(i)
        temp+=1
    return arr
            
            

def main():
    N,K,L=list(map(int,input().split()))
 
    graph1=[[]for _ in range(N)]
    graph2=[[]for _ in range(N)]
    for _ in range(K):
        p,q=list(map(int,input().split()))
        p-=1
        q-=1
        graph1[p].append(q)
        graph1[q].append(p)
    for _ in range(L):
        p,q=list(map(int,input().split()))
        p-=1
        q-=1
        graph2[p].append(q)
        graph2[q].append(p)
        
    a=dfs(N,graph1)
    b=dfs(N,graph2)
    
    dict={}
    for i in range(N):
        dict[(a[i],b[i])]=dict.get((a[i],b[i]),0)+1
    for i in range(N):
        print(dict[(a[i],b[i])],end=' ')
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque, Counter

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, K, L = map(int, input().split())
    Adj_r = [[] for i in range(N)]
    Adj_t = [[] for i in range(N)]

    for i in range(K):
        p, q = map(int, input().split())
        p, q = p-1, q-1
        Adj_r[p].append(q)
        Adj_r[q].append(p)

    for i in range(L):
        r, s = map(int, input().split())
        r, s = r-1, s-1
        Adj_t[r].append(s)
        Adj_t[s].append(r)

    col = 0
    cols_r = [None] * N
    cols_t = [None] * N

    for u in range(N):
        if cols_r[u] is None:
            bfs_color(N, Adj_r, cols_r, u, col)
            col += 1
        if cols_t[u] is None:
            bfs_color(N, Adj_t, cols_t, u, col)
            col += 1

    # debug(cols_r, locals())
    # debug(cols_t, locals())

    cnt = Counter((cols_r[u], cols_t[u]) for u in range(N))

    ans = [cnt[cols_r[u], cols_t[u]] for u in range(N)]

    print(*ans)


def bfs_color(N, Adj, v_cols, u, col):
    v_cols[u] = col
    nxts = deque([u])

    while nxts:
        v = nxts.popleft()

        for w in Adj[v]:
            if v_cols[w] is None:
                v_cols[w] = col
                nxts.append(w)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque


def create_group(N, n):
    city = [[] for _ in range(N + 1)]
    for _ in range(n):
        p, q = map(int, input().split(" "))
        city[p].append(q)
        city[q].append(p)

    group_list = [0] * (N + 1)
    gid = 0
    Q = deque()
    for i in range(1, N + 1):
        if group_list[i] == 0:
            gid += 1
            Q.clear()
            Q.append(i)
            group_list[i] = gid
            while len(Q) > 0:
                x = Q.popleft()
                for y in city[x]:
                    if group_list[y] == 0:
                        group_list[y] = gid
                        Q.append(y)

    return group_list

if __name__ == "__main__":
    N, K, L = list(map(int, input().split(" ")))
    rg = create_group(N, K)
    lg = create_group(N, L)

    rg_lg_dict = {}
    for i in range(1, N+1):
        key = (rg[i], lg[i])
        if key in rg_lg_dict:
            rg_lg_dict[key] += 1
        else:
            rg_lg_dict[key] = 1

    print_list = []
    for i in range(1, N+1):
        key = (rg[i], lg[i])
        print_list.append(str(rg_lg_dict[key]))
    print(" ".join(print_list))

Submission status: Accepted

Solution code:
from collections import deque

def makegroup(rg, n):
    city = [[] for i in range(N+1)]
    for i in range(n):
        p, q = map(int, input().split())
        city[p].append(q)
        city[q].append(p)

    Q = deque()
    gid = 0
    for i in range(1, N+1):
        if rg[i] == 0:
            gid += 1
            Q.clear()
            Q.append(i)
            rg[i] = gid
            while len(Q) > 0:
                x = Q.popleft()
                for y in city[x]:
                    if rg[y] == 0:
                        rg[y] = gid
                        Q.append(y)

N, K, L = map(int, input().split())
rg = [0] * (N + 1)
makegroup(rg, K)
lg = [0] * (N + 1)
makegroup(lg, L)

dict = {}
for i in range(1, N+1):
    key = (rg[i], lg[i])
    if key in dict:
        dict[key] += 1
    else:
        dict[key] = 1

key = (rg[1], lg[1])
print(dict[key], end="")
for i in range(2,N+1):
    key = (rg[i], lg[i])
    print(" ", dict[key], sep="", end="")
print()

Submission status: Accepted

Solution code:
class UnionFind:
	"""Union-Find, 
	http://www.slideshare.net/chokudai/union-find-49066733"""

	def __init__(self, N):
		self.par = [i for i in range(N)]
		self.rank = [0 for i in range(N)]

	def root(self, x):
		if(self.par[x]==x):
			return x
		else:
			self.par[x] = self.root(self.par[x])
			return self.par[x]

	def same(self, x, y):
		return self.root(x)==self.root(y)

	def unite(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x==y:
			return
		if self.rank[x]<self.rank[y]:
			self.par[x] = y
		else:
			self.par[y] = x
			if self.rank[x]==self.rank[y]:
				self.rank[x] = self.rank[x]+1
		return

N, K, L = map(lambda x:int(x), input().split())
P = [0]*K
Q = [0]*K
R = [0]*L
S = [0]*L
for i in range(K):
	P[i], Q[i] = map(lambda x:int(x), input().split())
for i in range(L):
	R[i], S[i] = map(lambda x:int(x), input().split())

uf_k = UnionFind(N)
uf_l = UnionFind(N)

for i in range(K):
	uf_k.unite(P[i]-1, Q[i]-1)
for i in range(L):
	uf_l.unite(R[i]-1, S[i]-1)

k_groups = [uf_k.root(i) for i in range(N)]
l_groups = [uf_l.root(i) for i in range(N)]

kl_groups = [(k_groups[i], l_groups[i]) for i in range(N)]
kl_groups_origin = kl_groups
kl_groups = sorted(kl_groups)

results_dict = {}

idx = 0
count = 1
pair = kl_groups[0]
for i in range(1, N):
	if kl_groups[i]==pair:
		count = count+1
	else:
		results_dict[pair] = count
		pair = kl_groups[i]
		count = 1
results_dict[pair] = count

for i in range(N):
	pair = kl_groups_origin[i]
	print(results_dict[pair], end=" ")

Submission status: Accepted

Solution code:
class UnionFind:
	"""Union-Find, 
	http://www.slideshare.net/chokudai/union-find-49066733"""

	def __init__(self, N):
		self.par = [i for i in range(N)]

	def root(self, x):
		if(self.par[x]==x):
			return x
		else:
			self.par[x] = self.root(self.par[x])
			return self.par[x]

	def same(self, x, y):
		return self.root(x)==self.root(y)

	def unite(self, x, y):
		x = self.root(x)
		y = self.root(y)
		# if x==y:
		# 	return
		self.par[x] = y
		return

N, K, L = map(lambda x:int(x), input().split())
P = [0]*K
Q = [0]*K
R = [0]*L
S = [0]*L
for i in range(K):
	P[i], Q[i] = map(lambda x:int(x), input().split())
for i in range(L):
	R[i], S[i] = map(lambda x:int(x), input().split())

uf_k = UnionFind(N)
uf_l = UnionFind(N)

for i in range(K):
	uf_k.unite(P[i]-1, Q[i]-1)
for i in range(L):
	uf_l.unite(R[i]-1, S[i]-1)

k_groups = [uf_k.root(i) for i in range(N)]
l_groups = [uf_l.root(i) for i in range(N)]

kl_groups = [(k_groups[i], l_groups[i]) for i in range(N)]
kl_groups_origin = kl_groups
kl_groups = sorted(kl_groups)

results_dict = {}

idx = 0
count = 1
pair = kl_groups[0]
for i in range(1, N):
	if kl_groups[i]==pair:
		count = count+1
	else:
		results_dict[pair] = count
		pair = kl_groups[i]
		count = 1
results_dict[pair] = count

for i in range(N):
	pair = kl_groups_origin[i]
	print(results_dict[pair], end=" ")

Submission status: Accepted

Solution code:
from collections import Counter
n,k,l = map(int, input().split())
def f(m):
    a = list(range(n))
    def g(i):
        if a[i] == i:
            return i
        a[i] = g(a[i])
        return a[i]
    for _ in range(m):
        p,q = map(int, input().split())
        i = g(p-1)
        j = g(q-1)
        a[j] = i
    return g
g = f(k)
h = f(l)
c = Counter((g(i),h(i)) for i in range(n))
print(' '.join((str(c[g(i),h(i)]) for i in range(n))))

Submission status: Accepted

Solution code:
from collections import Counter
n,k,l = map(int, input().split())
def f(m):
    a = list(range(n))
    def g(i):
        if a[i] == i:
            return i
        a[i] = g(a[i])
        return a[i]
    for _ in range(m):
        p,q = map(int, input().split())
        i = g(p-1)
        j = g(q-1)
        a[j] = i
    return g
g = f(k)
h = f(l)
c = Counter((g(i),h(i)) for i in range(n))
print(' '.join((str(c.get((g(i),h(i)), 1)) for i in range(n))))

Submission status: Accepted

Solution code:
#!/usr/bin/python

import sets
import sys

def find(parent, x):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent, parent[x])
        return parent[x]

def union(parent, x, y):
    find(parent, x)
    find(parent, y)

    if parent[x] != parent[y]:
        parent[parent[y]] = parent[parent[x]]

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split()

    while len(tokens) == 3:
        n, k, l = [int(i) for i in tokens]

        parent_roads = [int(i) for i in xrange(n)]
        parent_railways = [int(i) for i in xrange(n)]

        for i in xrange(k):
            x, y = [int(i) for i in raw_input().split(" ")]
            union(parent_roads, x - 1, y - 1)

        for i in xrange(l):
            x, y = [int(i) for i in raw_input().split(" ")]
            union(parent_railways, x - 1, y - 1)

        count = dict()
        for i in xrange(n):
            key = (find(parent_roads, i), find(parent_railways, i))
            if not count.has_key(key):
                count[key] = 0
            count[key] += 1

        results = []
        for i in xrange(n):
            key = (find(parent_roads, i), find(parent_railways, i))
            results.append(str(count[key]))
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split()

if __name__ == "__main__":
    main(sys.argv)

Submission status: Accepted

Solution code:
#!/usr/bin/python

import sets
import sys

def find(parent, x):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent, parent[x])
        return parent[x]

def union(parent, x, y):
    parent_x = find(parent, x)
    parent_y = find(parent, y)

    if parent_x != parent_y:
        parent[parent_y] = parent[parent_x]

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split()

    while len(tokens) == 3:
        n, k, l = [int(i) for i in tokens]

        parent_roads = [int(i) for i in xrange(n)]
        parent_railways = [int(i) for i in xrange(n)]

        for i in xrange(k):
            x, y = [int(i) for i in raw_input().split(" ")]
            union(parent_roads, x - 1, y - 1)

        for i in xrange(l):
            x, y = [int(i) for i in raw_input().split(" ")]
            union(parent_railways, x - 1, y - 1)

        count = dict()
        for i in xrange(n):
            key = (find(parent_roads, i), find(parent_railways, i))
            if not count.has_key(key):
                count[key] = 0
            count[key] += 1

        results = []
        for i in xrange(n):
            key = (find(parent_roads, i), find(parent_railways, i))
            results.append(str(count[key]))
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split()

if __name__ == "__main__":
    main(sys.argv)