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 Counter

class UnionFind:
    __slots__ = ['id']
    def __init__(self, n):
        self.id = [-1] * n
    def find(self, x):
        if self.id[x] < 0:
            return x
        else:
            self.id[x] = self.find(self.id[x])
            return self.id[x]
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.id[s1] <= self.id[s2]:
                self.id[s1] += self.id[s2]
                self.id[s2] = s1
            else:
                self.id[s2] += self.id[s1]
                self.id[s1] = s2
            return True
        return False
    def subsetall(self):
        a = []
        for i in range(len(self.id)):
            if self.id[i] < 0:
                a.append((i, -self.id[i]))
        return a

if __name__ == '__main__':
    N, K, L = map(int, input().split())

    uf_K = UnionFind(N)
    uf_L = UnionFind(N)
    for _ in [0] * K:
        p, q = map(int, input().split())
        uf_K.union(p - 1, q - 1)
    for _ in [0] * L:
        r, s = map(int, input().split())
        uf_L.union(r - 1, s - 1)

    keys, d = [], Counter()
    for i in range(N):
        key = uf_K.find(i), uf_L.find(i)
        keys.append(key)
        d[key] += 1

    print(*(d[key] for key in keys))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    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 = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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


n, k, l = map(int, input().split())

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

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

d = dict()
for i in range(n):
    f1 = uf1.find(i)
    f2 = uf2.find(i)
    t = (f1, f2)
    d[t] = d.get(t, 0) + 1

ans = []
for i in range(n):
    f1 = uf1.find(i)
    f2 = uf2.find(i)
    t = (f1, f2)
    ans.append(d[t])

print(*ans)

Submission status: Accepted

Solution code:
import sys
fin = sys.stdin.readline
from collections import defaultdict

class UnionFind(object):
    def __init__(self, N):
        self.__root = list(range(N))
    

    def root(self, x):
        if self.__root[x] == x:
            return x
        else:
            # root abbreviation
            self.__root[x] = self.root(self.__root[x])
            return self.__root[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.__root[x] = y
        return


N, K, L = [int(elem) for elem in fin().split(' ')]
road_list = tuple([tuple([int(elem)-1 for elem in fin().split(' ')]) for _ in range(K)])
train_list = tuple([tuple([int(elem)-1 for elem in fin().split(' ')]) for _ in range(L)])

uf_road = UnionFind(N)
uf_train = UnionFind(N)

for p, q in road_list:
    uf_road.unite(p, q)

for r, s in train_list:
    uf_train.unite(r, s)


key_list = []
count = defaultdict(int)
for i in range(N):
    # logN
    key = (uf_road.root(i), uf_train.root(i))
    key_list.append(key)
    count[key] += 1

assert len(key_list) == N
answer_list = [0] * N
for i, key in enumerate(key_list):
    answer_list[i] = str(count[key])
print(' '.join(answer_list))

Submission status: Accepted

Solution code:
from itertools import product
from collections import defaultdict as dd

class UFT(object):
  def __init__(self,n):
    self.parent={i:i for i in range(1,n+1)}
    self.height={i:0 for i in range(1,n+1)}
  def find(self,a):
    if self.parent[a]!=a:
      self.parent[a]=self.find(self.parent[a])
    return self.parent[a]
  def unite(self,a,b):
    a=self.find(a)
    b=self.find(b)
    if self.height[a]>self.height[b]:
      self.parent[b]=a
    else:
      if self.height[a]==self.height[b]:
        self.height[b]+=1
      self.parent[a]=b
  def isunited(self,a,b):
    return self.find(a)==self.find(b)


n,k,l=map(int,input().split())
uk=UFT(n)
ul=UFT(n)
dc=dd(int)
du={}

for _ in range(k):
  a,b=map(int,input().split())
  uk.unite(a,b)

for _ in range(l):
  a,b=map(int,input().split())
  ul.unite(a,b)
  
for i in range(1,n+1):
  du[i]=(uk.find(i),ul.find(i))
  dc[du[i]]+=1

print(*(dc[du[i]] for i in range(1,n+1)))

Submission status: Accepted

Solution code:
from collections import Counter
N,K,L = map(int,input().split())
roads = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(K)]
rails = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(L)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf_road = UnionFind(N)
for a,b in roads:
    if uf_road.is_same(a,b): continue
    uf_road.unite(a,b)

uf_rail = UnionFind(N)
for a,b in rails:
    if uf_rail.is_same(a,b): continue
    uf_rail.unite(a,b)

for i in range(N):
    uf_road.root(i)
    uf_rail.root(i)

ctr = Counter()
for i in range(N):
    r1 = uf_road.root(i)
    r2 = uf_rail.root(i)
    ctr[(r1,r2)] += 1

ans = []
for i in range(N):
    r1 = uf_road.root(i)
    r2 = uf_rail.root(i)
    ans.append(ctr[(r1,r2)])
print(*ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
    def find(self,x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                self.table[s1] += -1
                self.table[s2] = s1
        return
n,k,l = map(int, sys.stdin.readline().split())
p = []
for i in range(k):
    p.append(list(map(int, input().split())))
do = [[] for i in range(n+1)]
for pi in p:  #0-originedに注意
    do[pi[0]].append(pi[1])
p = []
for i in range(l):
    p.append(list(map(int, input().split())))
te = [[] for i in range(n+1)]
for pi in p:  #0-originedに注意
    te[pi[0]].append(pi[1])
dou = UnionFind(n)
for i in range(n+1):
  a = do[i]
  for j in a:
    dou.union(i-1,j-1)
douro = [-1] * n
for i in range(n):
  douro[i] = dou.find(i)
tet = UnionFind(n)
for i in range(n+1):
  a = te[i]
  for j in a:
    tet.union(i-1,j-1)
tetu = [-1] * n
for i in range(n):
  tetu[i] = tet.find(i)
d = defaultdict(int)
for i in range(n): 
  d[(douro[i],tetu[i])] += 1
ans = []
for i in range(n):
  ans.append(d[(douro[i],tetu[i])])
print(" ".join(map(str,ans)))

Submission status: Accepted

Solution code:
n, k, l = map(int,raw_input().split())

class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]

    def find(self,x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                self.table[s1] += -1
                self.table[s2] = s1
        return

uf_road = UnionFind(n)
uf_rail = UnionFind(n)

for i in range(k):
	f,t = map(int,raw_input().split()); f -= 1; t -= 1
	uf_road.union(f, t)

for i in range(l):
	f,t = map(int,raw_input().split()); f -= 1; t -= 1
	uf_rail.union(f, t)
road = [0]*n
rail = [0]*n
for i in range(n):
	road[i] = uf_road.find(i)
	rail[i] = uf_rail.find(i)

ans = {}

for i in range(n):
	key = (road[i],rail[i])
	count = ans.get(key)
	ans[key] = 1 if not count else count + 1

ret = []
for i in range(n):
	key = (road[i],rail[i])
	ret.append(str(ans.get(key)))

print ' '.join(ret)

Submission status: Accepted

Solution code:
n, k, l = map(int, input().split())
from collections import defaultdict

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

    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 x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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


uf1 = UnionFind(n)
uf2 = UnionFind(n)

for i in range(k):
    p, q = map(int, input().split())
    uf1.unite(p - 1, q - 1)


for i in range(l):
    r, s = map(int, input().split())
    uf2.unite(r - 1, s - 1)

pair = defaultdict(int)
for i in range(n):
    a = uf1.find(i)
    b = uf2.find(i)
    pair[(a, b)] += 1

ans = []
for i in range(n):
    ans.append(pair[(uf1.find(i), uf2.find(i))])

print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
class UnionFind(object):

    def __init__(self, N):
        self.N = N
        self.parent = list(range(self.N))
        self.rank = [0] * self.N
        self.size = [1] * self.N

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

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

        if self.rank[x] < self.rank[y]:
            x, y = y, x

        self.size[x] += self.size[y]
        self.parent[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

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

from collections import Counter
fn = lambda: map(int, input().split())
N, K, L = fn()
roads = UnionFind(N)
for i in range(K):
    pi, qi = fn()
    roads.union(pi-1, qi-1)
rails = UnionFind(N)
for i in range(L):
    ri, si = fn()
    rails.union(ri-1, si-1)
groups = []
for i in range(N):
    groups.append(str(roads.find(i)) + '-' + str(rails.find(i)))
c = Counter(groups)
print(*(c[g] for g in groups))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline


class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    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 = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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


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

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

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

c = defaultdict(int)
for i in range(N):
    x = uf1.find(i)
    y = uf2.find(i)
    c[(x, y)] += 1

for i in range(N):
    x = uf1.find(i)
    y = uf2.find(i)
    print(c[(x, y)], end=' ')
print()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            #print("x and y has already united")
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
                
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
from collections import defaultdict
import sys
sdin = sys.stdin.readline    

# 入力
n, k, l = map(int, sdin().split())

pq = []
for i in range(k):
    p, q = map(int, sdin().split())
    pq.append(tuple([p-1, q-1]))

rs = []
for i in range(l):
    r, s = map(int, sdin().split())
    rs.append(tuple([r-1, s-1]))

# 道路、鉄道についてそれぞれunion find
path = UnionFind(n)
for p, q in pq:
    path.unite(p, q)

rail = UnionFind(n)
for r, s in rs:
    rail.unite(r, s)

# (path.root, rail.root)の辞書作る
path_rail = defaultdict(int)
    
for i in range(n):
    path_rail[(path.find(i), rail.find(i))] += 1

# 表示する
ans = [path_rail[(path.find(i), rail.find(i))] for i in range(n)]
print(*ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

class UnionFind:
    def __init__(self, N):
        self.N = N
        self.parent = [i for i in range(N)]
        self.rank = [1]*(N)

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

    def is_group(self, x,y):
        return self.getroot(x) == self.getroot(y)

    def union(self, x, y):
        rootx = self.getroot(x)
        rankx = self.rank[rootx]
        rooty = self.getroot(y)
        ranky = self.rank[rooty]
        if rankx > ranky:
            self.parent[rooty] = rootx
        else:
            self.parent[rootx] = rooty
            self.rank[rooty] = max(self.rank[rooty], self.rank[rootx]+1)

n, k, l = map(int, input().split())

loads = UnionFind(n)
rails = UnionFind(n)

for _ in range(k):
    x, y = map(int, input().split())
    loads.union(x-1, y-1)

for _ in range(l):
    x, y = map(int, input().split())
    rails.union(x-1, y-1)

pair = defaultdict(int)
for i in range(n):
    pair[(loads.getroot(i), rails.getroot(i))] += 1

ans = "" 
for i in range(n-1):
    ans += str(pair[(loads.getroot(i), rails.getroot(i))]) + " "
ans += str(pair[(loads.getroot(n-1), rails.getroot(n-1))])
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, L, PQ, RS):
    ans = 0
    gr = defaultdict(list)
    for p, q in PQ:
        gr[p].append(q)
        gr[q].append(p)

    gt = defaultdict(list)
    for r, s in RS:
        gt[r].append(s)
        gt[s].append(r)

    ccr = {}
    unused = set(gr.keys())
    while unused:
        q = [unused.pop()]
        con = set([])
        while q:
            v = q.pop()
            con.add(v)
            for u in gr[v]:
                if u in unused:
                    q.append(u)
                    unused.remove(u)
        for v in con:
            ccr[v] = con

    cct = {}
    unused = set(gt.keys())
    while unused:
        q = [unused.pop()]
        con = set([])
        while q:
            v = q.pop()
            con.add(v)
            for u in gt[v]:
                if u in unused:
                    q.append(u)
                    unused.remove(u)
        for v in con:
            cct[v] = con

    cache = {}

    def cc(t, r):
        k = (id(t), id(r))
        if k not in cache:
            cache[k] = len(t & r)
        return cache[k]

    ans = []
    for i in range(1, N+1):
        if i in cct and i in ccr:
            a = cc(cct[i], ccr[i])
        else:
            a = 1
        ans.append(a)
    return " ".join(map(str, ans))


def main():
    N, K, L = read_int_n()
    PQ = [read_int_n() for _ in range(K)]
    RS = [read_int_n() for _ in range(L)]

    print(slv(N, K, L, PQ, RS))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
class UnionFind:
    #Union Find木のクラス

    def __init__(self, n):
        #親要素のノード番号を格納。par[x] == xのときそのノードはroot
        self.par = [i for i in range(n)]
        #木の高さ（初期状態では0）
        self.rank = [0] * n

    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 same(x, y):
        # xとyが同じ集合に属するかを判定
        return self.find(x) == self.find(y)

    def union(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


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

for i in range(K):
    pi, qi = map(lambda x: int(x) - 1, input().split())
    road.union(pi, qi)

for i in range(L):
    ri, si = map(lambda x: int(x) - 1, input().split())
    rail.union(ri, si)


road_and_rail = [(road.find(i), rail.find(i)) for i in range(N)]
count = Counter(road_and_rail)

ans = []
for i in range(N):
    ans.append(str(count.get(road_and_rail[i])))
print(' '.join(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict
N, K, L = map(int, input().split())
G = [[[], []] for i in range(N)]
R = [[i, i] for i in range(N)]
def root(i, j):
  if R[i][j] != i:
    R[i][j] = root(R[i][j], j)
  return R[i][j]
for i in range(K):
  p, q = map(int, input().split())
  rp = root(p - 1, 0)
  rq = root(q - 1, 0)
  if rp != rq:
    R[rp][0] = min(rp, rq)
    R[rq][0] = min(rp, rq)
for i in range(L):
  r, s = map(int, input().split())
  rr = root(r - 1, 1)
  rs = root(s - 1, 1)
  if rr != rs:
    R[rr][1] = min(rr, rs)
    R[rs][1] = min(rr, rs)
A = defaultdict(int)
for i in range(N):
  R[i][0] = root(i, 0)
  R[i][1] = root(i, 1)
  A[(R[i][0], R[i][1])] += 1
for i in range(N):
  print(A[(R[i][0], R[i][1])])

Submission status: Accepted

Solution code:
from collections import defaultdict

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


class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    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 = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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


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

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


c = defaultdict(int)
for i in range(N):
    c[(uf1.find(i), uf2.find(i))] += 1
for i in range(N):
    print(c[(uf1.find(i), uf2.find(i))])

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    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 union(self, x, y):
        x = self.root(x)
        y = self.root(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 same(self, x, y):
        return self.root(x) == self.root(y)

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

for _ in range(K):
    p,q = map(int,input().split())
    ufa.union(p,q)
for _ in range(L):
    r,s = map(int,input().split())
    ufb.union(r,s)

pairs = {}
for i in range(1,N+1):
    key = (ufa.root(i),ufb.root(i))
    if  key in pairs.keys():
        pairs[key] +=1
    else:
        pairs[key] =1
ans = []
for i in range(1,N+1):
    key = (ufa.root(i),ufb.root(i))
    ans.append(str(pairs[key]))
print(' '.join(ans))

Submission status: Accepted

Solution code:
from collections import deque

n, k, l = list(map(int, input().split()))

def get_groups(n, m):
    road = [[] for _ in range(n+1)]
    for _ in range(m):
        p, q = list(map(int, input().split()))
        road[p].append(q)
        road[q].append(p)

    groups = [0]*(n+1)
    group_idx = 1
    connect = deque()
    for i in range(1, n+1):
        if groups[i] == 0:
            groups[i] = group_idx
            connect.clear()
            connect.append(i)
            while len(connect) > 0:
                cnct = connect.popleft()
                for c in road[cnct]:
                    if groups[c] == 0:
                        groups[c] = group_idx
                        connect.append(c)
            group_idx += 1
            
    return groups

road_groups = get_groups(n, k)
train_groups = get_groups(n, l)
# print(road_groups, train_groups)
pairs = {}
for c in range(1, n+1):
    key = (road_groups[c], train_groups[c])
    if not key in pairs.keys():
        pairs[key] = 1
    else:
        pairs[key] += 1

ans = []
for c in range(1, n+1):
    key = (road_groups[c], train_groups[c])
    ans.append(str(pairs[key]))
print(' '.join(ans))

Submission status: Accepted

Solution code:
from collections import Counter

n, k, l = map(int, input().split())
ps = [tuple(map(int, input().split())) for _ in range(k)]
rs = [tuple(map(int, input().split())) for _ in range(l)]

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

union1 = {x:x for x in range(1, n+1)}
for p, q in ps:
    union1[root(p, union1)] = root(q, union1)

union2 = {x:x for x in range(1, n+1)}
for r, s in rs:
    union2[root(r, union2)] = root(s, union2)

gs = {x:(root(x, union1), root(x, union2)) for x in range(1, n+1)}
c = Counter(gs.values())
print(' '.join(str(c[gs[x]]) for x in range(1, n+1)))

Submission status: Accepted

Solution code:
N, k, l = map(int, input().split())

# UF木
class Uf:
    def __init__(self):
        self.Par = list(range(N + 1))

    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:
            self.Par[x] = y


K = Uf()
L = Uf()
for i in range(k):
    K.unite(*map(int, input().split()))
for i in range(l):
    L.unite(*map(int, input().split()))
U = [[i, K.root(i), L.root(i)] for i in range(1, N+1)]
from operator import itemgetter
U.sort(key=itemgetter(1, 2))
i = 0
while i < N:
    n = 1
    while i+n < N:
        if U[i+n][1:3] == U[i][1:3]:
            n += 1
        else:
            break
    for j in range(n):
        U[i+j].append(n)
    i += n
U.sort(key=itemgetter(0))
A = [u[3] for u in U]
print(" ".join(map(str, A)))

Submission status: Accepted

Solution code:
n, k, l = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(k)]
R = [[int(i) for i in input().split()] for j in range(l)]

class UnionFind():
  def __init__(self, elements):
    self.elements = elements
    self._root = {}
    for e in self.elements:
      self._root[e] = e
    
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if x != y:
      self._root[x] = y
    
  def root(self, x):
    if self._root[x] != x:
      self._root[x] = self.root(self._root[x])
    return self._root[x]
  
  def count(self):
    cnt = {}
    for e in self.elements:
      cnt[self.root(e)] += cnt.get(self.root(e), 0)
      
    for e in self.elements:
      yield cnt.get(e, 0)
      
  def get_union(self):
    union = {}
    for e in self.elements:
      if self.root(e) in union:
        union[self.root(e)].add(e)
      else:
        union[self.root(e)] = {e}
    return union
      
  
road = UnionFind(range(1, n+1))
rail = UnionFind(range(1, n+1))

for i in range(k):
  road.unite(P[i][0], P[i][1])
  
for i in range(l):
  rail.unite(R[i][0], R[i][1])

ans = {}
key = []
for e in range(1, n+1):
  key.append((road.root(e), rail.root(e)))
  ans[key[-1]] = ans.get(key[-1], 0) +1
  
for k in key:
  print(ans[k], end=' ')

Submission status: Accepted

Solution code:
n, k, l = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(k)]
R = [[int(i) for i in input().split()] for j in range(l)]

class UnionFind():
  def __init__(self, elements):
    self.elements = elements
    self._root = {}
    for e in self.elements:
      self._root[e] = e
    
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if not x == y:
      self._root[x] = y
    
  def root(self, x):
    if not self._root[x] == x:
      self._root[x] = self.root(self._root[x])
    return self._root[x]
  
  def count(self):
    cnt = {}
    for e in self.elements:
      cnt[self.root(e)] += cnt.get(self.root(e), 0)
      
    for e in self.elements:
      yield cnt.get(e, 0)
      
  def get_union(self):
    union = {}
    for e in self.elements:
      if self.root(e) in union:
        union[self.root(e)].add(e)
      else:
        union[self.root(e)] = {e}
    return union
      
  
road = UnionFind(range(1, n+1))
rail = UnionFind(range(1, n+1))

for i in range(k):
  road.unite(P[i][0], P[i][1])
  
for i in range(l):
  rail.unite(R[i][0], R[i][1])

ans = {}
key = []
for e in range(1, n+1):
  key.append((road.root(e), rail.root(e)))
  ans[key[-1]] = ans.get(key[-1], 0) +1
  
for k in key:
  print(ans[k], end=' ')

Submission status: Accepted

Solution code:
import sys
import itertools
from collections import defaultdict

sys.setrecursionlimit(10**8)

def find(x,table):	#xの根を返す	
	if table[x] == x:
		return x
	else:
		table[x] = find(table[x],table)	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def union(x,y,table,rank):	#xとyを繋げる
	x = find(x,table)	
	y = find(y,table)
	
	if x == y:
		return
	
	if rank[x] > rank[y]:
		table[y] = x
	else:
		table[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

def check(x,y,table):
	if find(x,table) == find(y,table):
		return True
	else:
		return False

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

table_car = [i for i in range(N)]	#木の親 table[x] == x なら根	
rank_car  = [1 for i in range(N)]	#木の長さ
table_tr  = [i for i in range(N)] 
rank_tr   = [1 for i in range(N)]

for i in range(0,K):
	a,b = map(int, input().split())
	union(a-1,b-1,table_car,rank_car)
	
for i in range(0,L):
	a,b = map(int, input().split())
	union(a-1,b-1,table_tr,rank_tr)
	
ar = [(find(i,table_car),find(i,table_tr)) 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)))