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
import sys
input = sys.stdin.readline


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def main():
    N, K, L = map(int, input().split())
    A = UnionFind(N)
    for _ in range(K):
        p, q = map(int, input().split())
        A.Unite(p, q)
    B = UnionFind(N)
    for _ in range(L):
        s, r = map(int, input().split())
        B.Unite(s, r)
    
    d = defaultdict(int)
    C = []
    for i in range(N):
        a = A.Find_Root(i+1)
        b = B.Find_Root(i+1)
        C.append(str(a)+","+str(b))
        d[C[i]] += 1
    # print(C)
    # print(d)

    ans = [str(d[c]) for c in C]
    print(" ".join(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
input = sys.stdin.readline


def main():
    n, k, l = map(int, input().split())
    p, q = [], []
    for _ in range(k):
        pi, qi = map(int, input().split())
        p.append(pi)
        q.append(qi)
    r, s = [], []
    for _ in range(l):
        ri, si = map(int, input().split())
        r.append(ri)
        s.append(si)

    road_tree = make_union_find(p, q, n)
    rail_tree = make_union_find(r, s, n)

    a, b = [], []
    x = defaultdict(int)
    for i in range(n):
        a.append(root(road_tree, i))
        b.append(root(rail_tree, i))
        key = (a[i], b[i])
        x[key] += 1

    for i in range(n):
        print(x[(a[i], b[i])], end=' ')

    # print("\n")
    # print(road_tree)
    # print(rail_tree)


def make_union_find(a, b, n):
    union_find_tree = [i for i in range(n)]

    for i in range(len(a)):
        x = root(union_find_tree, a[i] - 1)
        y = root(union_find_tree, b[i] - 1)
        if x != y:
            union_find_tree[x] = min(x, y)
            union_find_tree[y] = union_find_tree[x]

    return union_find_tree


# def make_union_find(a, b, n):
#     x = [i for i in range(n)]

#     for i in range(len(a)):
#         root = a[i] - 1
#         leaf = b[i] - 1
#         x[leaf] = root
#     return x


def root(union_find_tree, target):
    if union_find_tree[target] == target:
        return target
    else:
        union_find_tree[target] = root(
            union_find_tree, union_find_tree[target])
        return union_find_tree[target]


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
input = sys.stdin.readline


def main():
    n, k, l = map(int, input().split())
    p, q = [], []
    for _ in range(k):
        pi, qi = map(int, input().split())
        p.append(pi)
        q.append(qi)
    r, s = [], []
    for _ in range(l):
        ri, si = map(int, input().split())
        r.append(ri)
        s.append(si)

    road_tree = make_union_find(p, q, n)
    rail_tree = make_union_find(r, s, n)

    a, b = [], []
    x = defaultdict(int)
    for i in range(n):
        a.append(root(road_tree, i))
        b.append(root(rail_tree, i))
        key = (a[i], b[i])
        x[key] += 1

    for i in range(n):
        print(x[(a[i], b[i])], end=' ')


def make_union_find(a, b, n):
    union_find_tree = [i for i in range(n)]

    for i in range(len(a)):
        x = root(union_find_tree, a[i] - 1)
        y = root(union_find_tree, b[i] - 1)
        if x != y:
            union_find_tree[x] = y

    return union_find_tree


def root(union_find_tree, target):
    if union_find_tree[target] == target:
        return target
    else:
        union_find_tree[target] = root(
            union_find_tree, union_find_tree[target])
        return union_find_tree[target]


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def union(parent,size,a,b):
    x=find(parent,a)
    y=find(parent,b)
    if x!=y:
        if size[x]<size[y]:
            parent[x]=y 
            size[y]=size[x]+size[y]
        else:
            parent[y]=x 
            size[x]=size[x]+size[y]
    return parent,size 
def find(parent, a):
    while a != parent[a]:
            parent[a]=parent[parent[a]]
            a=parent[a]
    return a
n,k,l=map(int,input().split())
parent=[i for i in range(n)]
size=[1]*n
for i in range(k): 
    a,b=map(int,input().split())
    a-=1 
    b-=1 
    parent,size=union(parent,size,a,b)
parent2=[i for i in range(n)]
size2=[1]*n  
for i in range(l): 
    a,b=map(int,input().split())
    a-=1 
    b-=1 
    parent2,size2=union(parent2,size2,a,b)
from collections import defaultdict 
d=defaultdict(int)
for i in range(n):
    d[(find(parent,i),find(parent2,i))]+=1 
for i in range(n):
    a,b=find(parent,i),find(parent2,i)
    print(d[a,b],end=' ')

Submission status: Accepted

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

root_road = list(range(N))
root_rail = list(range(N))
depth_road = [1 for _ in range(N)]
depth_rail = [1 for _ in range(N)]

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

def unite(a,b,root,depth):
    A = find(a,root)
    B = find(b,root)
    if A == B:
        return
    elif depth[A] > depth[B]:
        root[B] = A
        depth[A] += depth[B]
    else:
        root[A] = B
        depth[B] += depth[A]

for i in range(K):
    p,q = map(int,input().split())
    unite(p-1,q-1,root_road,depth_road)
for i in range(L):
    r,s = map(int,input().split())
    unite(r-1,s-1,root_rail,depth_rail)
d = defaultdict(int)
pairs = []
for i in range(N):
    road = find(i,root_road)
    rail = find(i,root_rail)
    pairs.append((road,rail))
    d[(road,rail)] += 1
for p in pairs:
    print(d[p],end = " ")

Submission status: Accepted

Solution code:
import sys
import collections as c
sys.setrecursionlimit(10**6)

import sys
sys.setrecursionlimit(10**7)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N, K, L = map(int,input().split())
p = []
q = []
l = []
r = []

for _ in range(K):
	p_tmp, q_tmp = map(int ,input().split())
	p.append(p_tmp)
	q.append(q_tmp)

for _ in range(L):
	l_tmp, r_tmp = map(int, input().split())
	l.append(l_tmp)
	r.append(r_tmp)

road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
	road.Unite(p[i], q[i])

for i in range(L):
	train.Unite(l[i], r[i])

ar = []

for i in range(1,N+1):
	a = road.Find_Root(i)
	b = train.Find_Root(i)
	ar.append(str([a,b]))

Car = c.Counter(ar)

for i in range(N):
	print(Car[ar[i]], end = " ")

Submission status: Accepted

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

class UnionFind():
  def __init__(self,N):
    self.parents=list(range(N))
    self.size=[1]*N
  def find(self,x):
    if self.parents[x]==x:
      return x
    else:
      self.parents[x]=self.find(self.parents[x])
      return self.parents[x]
  def union(self,x,y):
    x,y=self.find(x),self.find(y)
    if x==y:
      return 
    if self.size[x]<self.size[y]:
      self.size[y]+=self.size[x]
      self.parents[x]=y
    else:
      self.size[x]+=self.size[y]
      self.parents[y]=x

uf1=UnionFind(N)
uf2=UnionFind(N)
for i in range(K):
  x,y=map(int,input().split())
  uf1.union(x-1,y-1)
for j in range(L):
  x,y=map(int,input().split())
  uf2.union(x-1,y-1)

keys=[(uf1.find(x),uf2.find(x)) for x in range(N)]
count={}
for key in keys:
  if key in count:
    count[key]+=1
  else:
    count[key]=1
print(*[count[key] for key in keys])

Submission status: Accepted

Solution code:
#初期値として、全ての要素が異なるグループ(要素番号＝グループ番号)
#に属するようにする。全ての要素が木の根になる。
class UnionFind():
    def __init__(self,n):
        self.par=[i for i in range(n+1)]
        self.rank=[0 for _ in range(n+1)]
        self.size=[1 for _ in range(n+1)]


#再帰的に木の根を求めることで、ある要素が属するグループを探索する。
    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.find(self.par[x])

#2つの要素が属するグループを結合する。xの子ノードとしてyを連結する。
    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
            self.size[x]+=self.size[y]

#2つの要素が同じグループに属するか否かは、findを用いると簡単に求まる。
    def is_same(self,x,y):
        return self.find(x)==self.find(y)

#xが属するグループの要素数    
    def get_size(self,x):
        x=self.find(x)
        return self.size[x]

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

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

#道路と鉄道の連結の組み合わせ(根のペアのカウント)
from collections import defaultdict
c=defaultdict(int)
for i in range(1,n+1):
    c[(uf1.find(i),uf2.find(i))]+=1
    #print(c[(uf1.find(i),uf2.find(i))])
for i in range(1,n+1):
    print(c[(uf1.find(i),uf2.find(i))])

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:
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

    def find(self, x):
        if self.uf[x]<0: return x
        self.uf[x] = self.find(self.uf[x])
        return self.uf[x]

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size(x) > self.size(y): x, y = y, x
        self.uf[y] += self.uf[x]
        self.uf[x] = y
        self.n -= 1

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

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

keys = [(uf1.find(x), uf2.find(x)) for x in range(N)]
count = {}
for key in keys:
    if key in count: count[key]+=1
    else: count[key]=1

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

Submission status: Accepted

Solution code:

def wantp(lis,n):

    q = []
    while lis[n] != n:
        q.append(n)
        n = lis[n]

    for i in q:
        lis[i] = n

    return n


N,K,L = map(int,input().split())
rp = [i for i in range(N)]
rank = [1 for i in range(N)]
pqlis = []

for i in range(K):

    P,Q = map(int,input().split())
    P -= 1
    Q -= 1

    PP = wantp(rp,P)
    QP = wantp(rp,Q)
    pqlis.append([P,Q])

    if PP != QP:

        if rank[PP] < rank[QP]:
            rp[PP] = QP

        elif rank[QP] < rank[PP]:
            rp[QP] = PP

        else:
            rp[QP] = PP
            rank[QP] += 1

#print (rp)

tp = [i for i in range(N)]
rank = [1 for i in range(N)]


for i in range(L):

    P,Q = map(int,input().split())
    P-=1
    Q-=1
    pqlis.append([P,Q])

    PP = wantp(tp,P)
    QP = wantp(tp,Q)

    #print (PP,QP,PP2,PQ2)

    if PP != QP:

        if rank[PP] < rank[QP]:
            tp[PP] = QP

        elif rank[QP] < rank[PP]:
            tp[QP] = PP

        else:
            tp[QP] = PP
            rank[QP] += 1

dic = {}

for i in range(N):

    p1 = wantp(rp,i)
    p2 = wantp(tp,i)
    string = str(p1) + "," + str(p2)

    if string not in dic:
        dic[string] = 1
    else:
        dic[string] += 1

for i in range(N):

    p1 = wantp(rp,i)
    p2 = wantp(tp,i)
    string = str(p1) + "," + str(p2)

    print (dic[string])

Submission status: Accepted

Solution code:
# DFS(深さ優先探索)
def create_links(N, K):
    links = [[] for _ in range(N)]
    for _ in range(K):
        p, q = map(int, input().split())
        links[p - 1].append(q - 1)
        links[q - 1].append(p - 1)
    return links


def create_groups(N, links):
    groups = list(range(N))
    for i in range(N):
        if groups[i] != i:
            continue
        q = [i]
        while q:
            j = q.pop()
            for k in links[j]:
                if groups[k] != i:
                    groups[k] = i
                    q.append(k)
    return groups


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

road_links = create_links(N, K)
rail_links = create_links(N, L)
road_groups = create_groups(N, road_links)
rail_groups = create_groups(N, rail_links)

d = {}
for i in range(N):
    t = (road_groups[i], rail_groups[i])
    if t in d:
        d[t] += 1
    else:
        d[t] = 1

print(*[d[(road_groups[i], rail_groups[i])] for i in range(N)])

Submission status: Accepted

Solution code:
# Union Find 木
def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


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

roads = [-1] * N
rails = [-1] * N

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

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

d = {}
for i in range(N):
    t = (find(roads, i), find(rails, i))
    if t in d:
        d[t] += 1
    else:
        d[t] = 1

print(*[d[(find(roads, i), find(rails, i))] for i in range(N)])

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]


N,K,L = map(int, input().split())
road_list = []
for i in range(K):
    road_list.append([int(x) for x in input().split()])
train_list = []
for i in range(L):
    train_list.append([int(x) for x in input().split()])
    
road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
    road.unite(road_list[i][0], road_list[i][1])
    
for i in range(L):
    train.unite(train_list[i][0], train_list[i][1])
    
R = [i for i in range(N+1)]
T = [i for i in range(N+1)]

for i in range(1, N+1):
    R[i] = road.find_root(i)
    T[i] = train.find_root(i)
    
pair = [0 for i in range(N+1)]
for i in range(1, N+1):
    pair[i] = (R[i], T[i])
    
dic = {}
for i in range(1, N+1):
    if pair[i] in dic:
        dic[pair[i]] += 1
    else:
        dic[pair[i]] = 1
        
for i in range(1, N+1):
    print(dic[pair[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 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 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_check(self, x, y):
        return self.find(x) == self.find(y)

from collections import defaultdict

n,k,l=map(int,input().split())
load=UnionFind(n)
train=UnionFind(n)
for i in range(k):
    a,b=map(int,input().split())
    load.union(a,b)
for i in range(l):
    a,b=map(int,input().split())
    train.union(a,b)

ar=[(load.find(i),train.find(i)) for i in range(1,n+1)]
dic=defaultdict(int)

for i in ar:
    dic[i]+=1

ans=[]
for i in range(n):
    ans.append(dic[ar[i]])
print(*ans)

Submission status: Accepted

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

def find(list_path, x):
  if list_path[x] != x:
    list_path[x] = find(list_path, list_path[x])
  return list_path[x]

def union(list_path, x, y):
  x = find(list_path, x)
  y = find(list_path, y)
  if x != y:
    list_path[x] = min(x, y)
    list_path[y] = list_path[x]

list_road = [i for i in range(n)]
for _ in range(k):
  p, q = map(int, input().split(" "))
  union(list_road, (p - 1), (q - 1))
list_rail = [i for i in range(n)]
for _ in range(l):
  r, s = map(int, input().split(" "))
  union(list_rail, (r - 1), (s - 1))

dict_num_connect = {}
for i in range(n):
  dict_num_connect[list_road[i], list_rail[i]] = dict_num_connect.get(
      (find(list_road, i), find(list_rail, i)), 0) + 1

print(" ".join(str(dict_num_connect[list_road[i], list_rail[i]]) 
               for i in range(n)))

Submission status: Accepted

Solution code:
from collections import defaultdict


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


N, K, L = map(int, input().split())
UFc = UnionFind(N)
UFt = UnionFind(N)
for _ in range(K):
    p, q = map(int, input().split())
    UFc.unite(p, q)
for _ in range(L):
    p, q = map(int, input().split())
    UFt.unite(p, q)

gr = [0] * (N + 1)
cnt = defaultdict(int)
for i in range(1, N + 1):
    gr[i] = UFc.find_root(i) * (N + 1) + UFt.find_root(i)
    cnt[gr[i]] += 1

ans = [0] * N
for i in range(1, N + 1):
    ans[i-1] = cnt[gr[i]]

print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return False
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)
    return True

class Node:
    def __init__(self, id):
        self.id = id
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        # if self.is_root:
        #     return self
        # elif self.parent.is_root:
        #     return self.parent
        # else:
        #     self.parent = self.parent.root()
        #     return self.parent
        node = self
        while not node.is_root:
            node = node.parent
        return node

def main():
    N, K, L = map(int, input().split())
    
    trains = [Node(i) for i in range(N)]
    streets = [Node(i) for i in range(N)]

    for i in range(K):
        p, q = map(int, input().split())
        p -= 1; q -= 1
        unite(trains[p], trains[q])
    for i in range(L):
        r, s = map(int, input().split())
        r -= 1; s -= 1
        unite(streets[r], streets[s])
    dic = {}
    roots = []
    for i in range(N):
        tmp = (trains[i].root().id, streets[i].root().id)
        roots.append(tmp)
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1
    
    for i in range(N-1):
        print(dic[roots[i]], end=" ")
    print(dic[roots[N-1]])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return False
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)
    return True

class Node:
    def __init__(self, id):
        self.id = id
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        if self.is_root:
            return self
        elif self.parent.is_root:
            return self.parent
        else:
            self.parent = self.parent.root()
            return self.parent

def main():
    N, K, L = map(int, input().split())
    
    trains = [Node(i) for i in range(N)]
    streets = [Node(i) for i in range(N)]

    for i in range(K):
        p, q = map(int, input().split())
        p -= 1; q -= 1
        unite(trains[p], trains[q])
    for i in range(L):
        r, s = map(int, input().split())
        r -= 1; s -= 1
        unite(streets[r], streets[s])
    dic = {}
    roots = []
    for i in range(N):
        tmp = (trains[i].root().id, streets[i].root().id)
        roots.append(tmp)
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1
    
    for i in range(N-1):
        print(dic[roots[i]], end=" ")
    print(dic[roots[N-1]])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)

        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[y] = x
        else:
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    def Count(self, x):
        return -self.root[self.Find_Root(x)]

def main():
  N, K, L = map(int, input().split())
  U_road = UnionFind(N)
  U_train = UnionFind(N)
  for _ in range(K):
    p, q = map(int, input().split())
    U_road.Unite(p, q)
  for _ in range(L):
    r, s = map(int, input().split())
    U_train.Unite(r, s)
  connect_dict = {}
  for i in range(1, N+1):
    x, y = U_road.Find_Root(i), U_train.Find_Root(i)
    if (x, y) in connect_dict:
      connect_dict[(x, y)] += 1
    else:
      connect_dict[(x, y)] = 1
  ans = []
  for i in range(1, N+1):
    x, y = U_road.Find_Root(i), U_train.Find_Root(i)
    ans.append(connect_dict[(x, y)])
  ans = list(map(str, ans))
  print(' '.join(ans))

  

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10*5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

class UnionFind():

    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)

        if(x == y):
            return 

        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1


    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    def Count(self, x):
        return -self.root[self.Find_Root(x)]

n, k, l = MAP()
road = [0]*k
train = [0]*l
for i in range(k):
    p, q = MAP()
    road[i] = (p,q)
for i in range(l):
    r, s = MAP()
    train[i] = (r,s)

ans = [0]*n

uf_road = UnionFind(n)
uf_train = UnionFind(n)

for i in range(k):
    uf_road.Unite(road[i][0]-1, road[i][1]-1)
for i in range(l):
    uf_train.Unite(train[i][0]-1, train[i][1]-1)

roots = [(0,0)]*n
for i in range(n):
    a = uf_road.Find_Root(i)
    b = uf_train.Find_Root(i)
    roots[i] = (a, b)

c = Counter(roots)
for i in range(n):
    ans[i] = c[roots[i]]

for i in range(n):
    print(str(ans[i]) + " ", end = "")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.ranks = [[0] * n, [0] * n]
        self.pars = [[i for i in range(n)], [i for i in range(n)]]
        self.n = n

    def find_set(self, node, idx):
        if self.pars[idx][node] == node:
            return node
        else:
            self.pars[idx][node] = self.find_set(self.pars[idx][node], idx)
            return self.pars[idx][node]

    def same_set(self, x, y, idx):
        return self.find_set(x, idx) == self.find_set(y, idx)

    def unite(self, x, y, idx):
        x = self.find_set(x, idx)
        y = self.find_set(y, idx)
        if x == y:
            return
        if self.ranks[idx][x] > self.ranks[idx][y]:
            self.pars[idx][y] = x
        else:
            self.pars[idx][x] = y
            if self.ranks[idx][x] == self.ranks[idx][y]:
                self.ranks[idx][y] += 1


def main():
    n, k, l = map(int, input().split())
    uf = UnionFind(n)
    road = 0
    train = 1

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

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

    roots = [(uf.find_set(i, road), uf.find_set(i, train)) for i in range(n)]
    c = Counter(roots)
    ans = []
    for root in roots:
        ans.append(c[root])

    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

PM = [[] for i in range(n+1)]
RM = [[] for i in range(n+1)]

for i in range(k):
    PM[P[i][0]].append(P[i][1])
    PM[P[i][1]].append(P[i][0])
for i in range(l):
    RM[R[i][0]].append(R[i][1])
    RM[R[i][1]].append(R[i][0])

C = [[0] * 2 for i in range(n+1)]

VP = [0] * (n+1)
clr = 0
for i in range(1, n+1):
    if VP[i] == 0:
        VP[i] = 1
        clr += 1
        Q = [i]
        st = 0
        while st < len(Q):
            j = Q[st]
            C[j][0] = clr
            for item in PM[j]:
                if VP[item] == 0:
                    VP[item] = 1
                    Q.append(item)
            st += 1

VR = [0] * (n+1)
clr = 0
for i in range(1, n+1):
    if VR[i] == 0:
        VR[i] = 1
        clr += 1
        Q = [i]
        st = 0
        while st < len(Q):
            j = Q[st]
            C[j][1] = clr
            for item in RM[j]:
                if VR[item] == 0:
                    VR[item] = 1
                    Q.append(item)
            st += 1

# print(C)

D = {}
for i in range(1, n+1):
    try:
        D[(C[i][0], C[i][1])] += 1
    except:
        D[(C[i][0], C[i][1])] = 1

ANS = []

for i in range(1, n+1):
    ANS.append(str(D[(C[i][0], C[i][1])]))

print(" ".join(ANS))