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
N, K, L = map(int,input().split())
data = [[0, 0] for _ in range(N)]
Lpath = [[] for _ in range(N)]
Tpath = [[] for _ in range(N)]

for _ in range(K):
    p, q = map(int,input().split())
    p -= 1
    q -= 1
    Lpath[p].append(q)
    Lpath[q].append(p)
    
for _ in range(L):
    r, s = map(int,input().split())
    r -= 1
    s -= 1
    Tpath[r].append(s)
    Tpath[s].append(r)
    
for i in range(N):
    if data[i][0]:
        continue
    data[i][0] = i + 1
    stack = [i]
    while stack:
        s = stack.pop()
        for to in Lpath[s]:
            if data[to][0]:
                continue
            data[to][0] = i + 1
            stack.append(to)

for i in range(N):
    if data[i][1]:
        continue
    data[i][1] = i + 1
    stack = [i]
    while stack:
        s = stack.pop()
        for to in Tpath[s]:
            if data[to][1]:
                continue
            data[to][1] = i + 1
            stack.append(to)

ans = [0] * N
d = defaultdict(int)         
for i in range(N):
    d[tuple(data[i])] += 1
for i in range(N):
    ans[i] = d[tuple(data[i])]

print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from collections import Counter


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

GRAPH = [[] for _ in range(n + 1)]
for _ in range(k):
    p, q = map(int, input().split())
    GRAPH[p].append(q); GRAPH[q].append(p)

def dfs(now):
    A[now] = a
    SEARCHED[now] = True
    for v in GRAPH[now]:
        if SEARCHED[v]:
            continue
        next = v
        dfs(next)

A = [0] * (n + 1)
SEARCHED = [False] * (n + 1)

a = 1
for i in range(1, n + 1):
    if SEARCHED[i]:
        continue
    dfs(i)
    a += 1

GRAPH = [[] for _ in range(n + 1)]
for _ in range(l):
    r, s = map(int, input().split())
    GRAPH[r].append(s); GRAPH[s].append(r)

def dfs(now):
    B[now] = b
    SEARCHED[now] = True
    for v in GRAPH[now]:
        if SEARCHED[v]:
            continue
        next = v
        dfs(next)

B = [0] * (n + 1)
SEARCHED = [False] * (n + 1)

b = 1
for i in range(1, n + 1):
    if SEARCHED[i]:
        continue
    dfs(i)
    b += 1

AB = [ab for ab in zip(A, B)]
COUNTS = Counter(AB)

for i in range(1, n + 1):
    print(COUNTS[AB[i]])

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 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())

n, k, l = map(int, input().split())
uf_road = UnionFind(n)
uf_train = UnionFind(n)
connect = {}

for _ in range(k):
  p, q = map(lambda x:int(x)-1, input().split())
  uf_road.Unite(p, q)

for _ in range(l):
  r, s = map(lambda x:int(x)-1, input().split())
  uf_train.Unite(r, s)

for i in range(n):
  par1, par2 = uf_road.Find_Root(i), uf_train.Find_Root(i)
  if (par1, par2) in connect.keys():
    connect[(par1, par2)] += 1
  else:
    connect[(par1, par2)] = 1

ans = []
for i in range(n):
  par1, par2 = uf_road.Find_Root(i), uf_train.Find_Root(i)
  ans += [str(connect[(par1, par2)])]

print(" ".join(ans))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, elements):
        self.elements = elements

    def same(self, a, b):
        return self.find(a) == self.find(b)

    def find(self, a):
        parent = self.elements[a]
        if parent < 0:
            return a
        self.elements[a] = self.find(parent)
        return self.elements[a]

    def unite(self, a, b):
        a_parent = self.find(a)
        b_parent = self.find(b)

        # already same union
        if a_parent == b_parent:
            return

        self.elements[a_parent] += self.elements[b_parent]
        self.elements[b_parent] = a_parent


N, K, L = map(int, input().split())
road_union = UnionFind([-1 for i in range(N)])
for _ in range(K):
    a, b = map(int, input().split())
    road_union.unite(a - 1, b - 1)

train_union = UnionFind([-1 for i in range(N)])
for _ in range(L):
    a, b = map(int, input().split())
    train_union.unite(a - 1, b - 1)

ma = dict()
for i in range(N):
    p = (road_union.find(i), train_union.find(i))
    ma[p] = ma.get(p, 0) + 1

for i in range(N):
    p = (road_union.find(i), train_union.find(i))
    print(ma[p], end=' ')

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, elements):
        self.elements = {e: -1 for e in elements}

    def same(self, a, b):
        return self.find(a) == self.find(b)

    def find(self, a):
        parent = self.elements[a]
        if parent < 0:
            return a
        self.elements[a] = self.find(parent)
        return self.elements[a]

    def unite(self, a, b):
        a_parent = self.find(a)
        b_parent = self.find(b)

        # already same union
        if a_parent == b_parent:
            return

        self.elements[a_parent] += self.elements[b_parent]
        self.elements[b_parent] = a_parent


N, K, L = map(int, input().split())
road_union = UnionFind(i for i in range(1, N + 1))
for _ in range(K):
    a, b = map(int, input().split())
    road_union.unite(a, b)

train_union = UnionFind(i for i in range(1, N + 1))
for _ in range(L):
    a, b = map(int, input().split())
    train_union.unite(a, b)

ma = dict()
for i in range(N):
    p = (road_union.find(i + 1), train_union.find(i + 1))
    ma[p] = ma.get(p, 0) + 1

for i in range(N):
    p = (road_union.find(i + 1), train_union.find(i + 1))
    print(ma[p], end=' ')

Submission status: Accepted

Solution code:
class UnionFindTree():
    # Union find tree
    # 2つの効率化　経路圧縮、ランク
    # つなげることはできるか分離することはできないので、木をつなげる方向に利用する
    # 
    def __init__(self, node_size):
        # node_num: 全体のノード数
        # parent: ノードがrootなら-1、親がいれば親の番号を入れる
        # size:
        # rank:  
        # self.parent =[-1] * node_size
        self.parent =[x for x in range(node_size)]
        self.node_size = node_size
        self.size = [1] * node_size
        self.rank = [1] * node_size

        # self.node_list = np.array([x for x in range(node_size)])
        self.member_dict = {}
    
    def find_root(self,node):
        # node属する木のrootを探す
        # たどった経路に含まれるnodeの親をrootにつなぎ替える
        if self.parent[node] == node:             # 自身がrootの場合
            root = node
        else:                                   # 自身がrootでない場合
            root = self.find_root(self.parent[node]) # 再帰的にrootを探す
            self.parent[node] = root            # たどった経路に含まれるnodeの親をrootにつなぎ替える(経路圧縮)
        return root

    def unite(self,node0, node1):
        # node0とnode1が含まれる木を結合する
        
        #node0 node1のrootを求める
        root_node0 = self.find_root(node0) 
        root_node1 = self.find_root(node1)

        if root_node0 != root_node1:
            # rankを比較しrankが小さい方の木を大きい方の木のrootにつなげる
            # rank is sameのときのみrankが増える

            # node1のグループをnode0のグループに結合
            if self.rank[root_node0] == self.rank[root_node1]: # rank is same
                self.parent[root_node1] = root_node0
                self.rank[root_node0] += 1
                self.size[root_node0] += self.size[root_node1]

            # node1のグループをnode0のグループに結合
            elif self.rank[root_node0] > self.rank[root_node1]:
                self.parent[root_node1] = root_node0
                self.size[root_node0] += self.size[root_node1]

            # node0のグループをnode1のグループに結合
            else:
                self.parent[root_node0] = root_node1
                self.size[root_node1] += self.size[root_node0]

    def same(self,node0,node1):
        #同じグループか確かめる
        return self.find_root(node0)==self.find_root(node1)




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

road_uft = UnionFindTree(N)
train_uft = UnionFindTree(N)

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

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


pair_dict = {}
pair_list = []
for i in range(N):
    road_root = road_uft.find_root(i)
    train_root = train_uft.find_root(i)
    pair = (road_root,train_root)
    pair_list.append(pair)
    if pair in pair_dict:
        pair_dict[pair] +=1
    else:
        pair_dict[pair] = 1

ans = ""
for i in range(N):
    pair = pair_list[i]
    ans += str(pair_dict[pair]) + " "
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = lambda: sys.stdin.readline().rstrip()

class UnionFind:
    
    def __init__(self, n):
        self.parents = [-1]*n

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

    def union(self, x, y):

        x = self.find(x)
        y = self.find(y)  

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x,y = y,x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

road_union = UnionFind(N)
rails_union = UnionFind(N)

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

    road_union.union(p,q)
for i in range(L):
    r,s = map(int, input().split())

    r -= 1
    s -= 1
    rails_union.union(r,s)

d = defaultdict(int)

for i in range(N):
    d[(road_union.find(i), rails_union.find(i))] += 1


print(*[d[(road_union.find(i),rails_union.find(i))] for i in range(N)])

Submission status: Accepted

Solution code:

class UnionFindTree():
    # Union find tree
    # 2つの効率化　経路圧縮、ランク
    # つなげることはできるか分離することはできないので、木をつなげる方向に利用する
    # 
    def __init__(self, node_size):
        # node_num: 全体のノード数
        # parent: ノードがrootなら-1、親がいれば親の番号を入れる
        # size:
        # rank:  
        # self.parent =[-1] * node_size
        self.parent =[x for x in range(node_size)]
        self.node_size = node_size
        self.size = [1] * node_size
        self.rank = [1] * node_size

        # self.node_list = np.array([x for x in range(node_size)])
        self.member_dict = {}
    
    def find_root(self,node):
        # node属する木のrootを探す
        # たどった経路に含まれるnodeの親をrootにつなぎ替える
        if self.parent[node] == node:             # 自身がrootの場合
            root = node
        else:                                   # 自身がrootでない場合
            root = self.find_root(self.parent[node]) # 再帰的にrootを探す
            self.parent[node] = root            # たどった経路に含まれるnodeの親をrootにつなぎ替える(経路圧縮)
        return root

    def unite(self,node0, node1):
        # node0とnode1が含まれる木を結合する
        
        #node0 node1のrootを求める
        root_node0 = self.find_root(node0) 
        root_node1 = self.find_root(node1)

        if root_node0 != root_node1:
            # rankを比較しrankが小さい方の木を大きい方の木のrootにつなげる
            # rank is sameのときのみrankが増える

            # node1のグループをnode0のグループに結合
            if self.rank[root_node0] == self.rank[root_node1]: # rank is same
                self.parent[root_node1] = root_node0
                self.rank[root_node0] += 1
                self.size[root_node0] += self.size[root_node1]

            # node1のグループをnode0のグループに結合
            elif self.rank[root_node0] > self.rank[root_node1]:
                self.parent[root_node1] = root_node0
                self.size[root_node0] += self.size[root_node1]

            # node0のグループをnode1のグループに結合
            else:
                self.parent[root_node0] = root_node1
                self.size[root_node1] += self.size[root_node0]

    def same(self,node0,node1):
        #同じグループか確かめる
        return self.find_root(node0)==self.find_root(node1)




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

road_uft = UnionFindTree(N)
train_uft = UnionFindTree(N)

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

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


pair_dict = {}
pair_list = []
for i in range(N):
    road_root = road_uft.find_root(i)
    train_root = train_uft.find_root(i)
    pair = (road_root,train_root)
    pair_list.append(pair)
    if pair in pair_dict:
        pair_dict[pair] +=1
    else:
        pair_dict[pair] = 1

ans = ""
for i in range(N):
    pair = pair_list[i]
    ans += str(pair_dict[pair]) + " "
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N,K,L = map(int, input().split())
    class UnionFind():
        #n個の要素を番号0~n-1で管理する
        #parents:要素の親(1つ上), 要素が根の場合サイズを表す
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        #要素xの根を返す, その過程で経路圧縮も行う
        def find(self, x):
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)
            if x == y:
                return
            #それぞれのsizeで比べる
            if self.parents[x] > self.parents[y]:
                x, y = y, x
            self.parents[x] += self.parents[y]
            self.parents[y] = x #根をくっつける(片方を親にする)

        #xが属するグループのsize
        def size(self, x):
            return -self.parents[self.find(x)]

        #xとyが同じグループかどうか
        def same(self, x, y):
            return self.find(x) == self.find(y)

        #xが属するグループの要素全てを返す
        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]
        
    douro = UnionFind(N+1)
    tetudou = UnionFind(N+1)
    for _ in range(K):
        p,q = map(int, input().split())
        douro.union(p,q)
    for _ in range(L):
        r,s = map(int, input().split())
        tetudou.union(r,s)
    dic = {}
    parlis = []
    for i in range(1, N+1):
        p1 = douro.find(i)
        p2 = tetudou.find(i)
        parlis.append((p1,p2))
        if (p1,p2) in dic:
            dic[(p1,p2)] += 1
        else: 
            dic[(p1,p2)] = 1
    print(' '.join([str(dic[parlis[i]]) for i in range(N)]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
    
    def isSame(self, x, y):
        return self.find(x) == self.find(y)

from collections import defaultdict
def solve():
    N, K, L = map(int, input().split())
    road_uf = UnionFind(N)
    train_uf = UnionFind(N)

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

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

    ma = defaultdict(int)
    for v in range(N):
        root_road = road_uf.find(v)
        root_train = train_uf.find(v)
        ma[str(root_road) + "_" + str(root_train)] += 1
    
    for v in range(N):
        root_road = road_uf.find(v)
        root_train = train_uf.find(v)
        print(ma[str(root_road) + "_" + str(root_train)], end=' ')

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

R=[[] for i in range(N)]
T=[[] for i in range(N)]


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を見てくっつける方を決める
      #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)]

uniR=UnionFind(N)
for i in range(K):
  p,q=map(int, input().split())
  R[p-1].append(q-1)
  R[q-1].append(p-1)
  
  uniR.Unite(p-1,q-1)
uniT=UnionFind(N)  
for i in range(L):
  r, s=map(int, input().split())
  T[r-1].append(s-1)
  T[s-1].append(r-1)
  
  uniT.Unite(r-1,s-1)
dic = {}  
for i in range(N):
    val = (uniR.Find_Root(i), uniT.Find_Root(i))
    if val in dic:
        dic[val] += 1
    else:
        dic[val] = 1
        
for i in range(N):
    print(dic[(uniR.Find_Root(i), uniT.Find_Root(i))], end=" ")

Submission status: Accepted

Solution code:
from collections import defaultdict
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n,k,l = map(int,input().split())
road = [list(map(int,input().split())) for i in range(k)]
train = [list(map(int,input().split())) for i in range(l)]
rg = [[] for i in range(n+1)]
rv = [0 for i in range(n+1)]
tg = [[] for i in range(n+1)]
tv = [0 for i in range(n+1)]
def connect(road,rg,rv):
  for a,b in road:
    rg[a].append(b)
    rg[b].append(a)
  cnt = 0
  for i in range(1,n+1):
    if rv[i] == 0:
      cnt += 1
      stack = [i]
      while stack:
        x = stack.pop()
        rv[x] = cnt
        for y in rg[x]:
          if rv[y] == 0:
            stack.append(y)
            rv[y] = cnt
connect(road,rg,rv)
connect(train,tg,tv)
condc = defaultdict(list)
for i in range(1,n+1):
  cr = rv[i]
  ct = tv[i]
  condc[(cr,ct)].append(i)
ans = []
for i in range(1,n+1):
  cr = rv[i]
  ct = tv[i]
  ans.append(len(condc[(cr,ct)]))
print(*ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.d = [-1] * n

    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        else:
            if self.d[x] > self.d[y]:
                x, y = y, x
            self.d[x] += self.d[y]
            self.d[y] = x
            return True

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


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


n, k, l = map(int, input().split())
uf1 = UnionFind(n)
for i in range(k):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    uf1.unite(p, q)
uf2 = UnionFind(n)
for i in range(l):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    uf2.unite(r, s)
dic = {}
for i in range(n):
    val = (uf1.find(i), uf2.find(i))
    if val in dic:
        dic[val] += 1
    else:
        dic[val] = 1

for i in range(n):
    print(dic[(uf1.find(i), uf2.find(i))])

Submission status: Accepted

Solution code:
from collections import defaultdict

def find(x, parent):
    if parent[x] == x:
        return x
    else:
        # keyとvalueが同じ位置に当たるまで親をたどる
        parent[x] = find(parent[x], parent)
        return parent[x]

# 併合
def unite(x, y, parent):
    x = find(x, parent)
    y = find(y, parent)
    if x == y: return

    parent[y] = x

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

    for _ in range(K):
        a, b = map(int, input().split())
        unite(a-1, b-1, street)

    for _ in range(L):
        a, b = map(int, input().split())
        unite(a-1, b-1, train)

    d = defaultdict(int)
    for i in range(N):
        a = find(street[i], street)
        b = find(train[i], train)
        d[(a, b)] += 1

    ans = []
    for i in range(N):
        a = find(street[i], street)
        b = find(train[i], train)
        ans.append(str(d[(a, b)]))

    print(' '.join(ans))

solve()

Submission status: Accepted

Solution code:
from collections import defaultdict

def find(x, parent):
    if parent[x] == x:
        return x
    else:
        # keyとvalueが同じ位置に当たるまで親をたどる
        parent[x] = find(parent[x], parent)
        return parent[x]

# 併合
def unite(x, y, parent):
    x = find(x, parent)
    y = find(y, parent)
    if x == y: return

    parent[y] = x

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

    for _ in range(K):
        a, b = map(int, input().split())
        unite(a-1, b-1, street)

    for _ in range(L):
        a, b = map(int, input().split())
        unite(a-1, b-1, train)

    d = defaultdict(int)
    for i in range(N):
        a = find(street[i], street)
        b = find(train[i], train)
        d[(a, b)] += 1

    ans = []
    for i in range(N):
        a = find(street[i], street)
        b = find(train[i], train)
        ans.append(str(d[a, b]))

    print(' '.join(ans))

solve()

Submission status: Accepted

Solution code:
maxn = 2 * (10**5)

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

par = [[0] * (n+1) for _ in range(2)]
rank = [[0] * (n+1) for _ in range(2)]

#初期化
for i in range(n+1):
    par[0][i] = i
    rank[0][i] = 0
    par[1][i] = i
    rank[1][i] = 0

#判定(一番上野根を求める)
def find(num,x):
    if par[num][x] == x:
        return x
    else:
        par[num][x] = find(num,par[num][x])
        return par[num][x]
    
#結合
def unite(num , x , y):
    rx = find(num,x)
    ry = find(num,y)
    
    if rx == ry:
        return
    
    if rank[num][rx] < rank[num][ry]:
        par[num][rx] = ry
    elif rank[num][rx] > rank[num][ry]:
        par[num][ry] = rx
    else:
        par[num][ry] = x
        rank[num][rx] += 1
        

for i in range(k):
    p,q = map(int, input().split())
    unite(0,p,q)
        
for i in range(l):
    r,s = map(int, input().split())
    unite(1,r,s)
    
pairs = [(find(0,i),find(1,i)) for i in range(1,n+1)]
from collections import Counter
pairc = Counter(pairs)
ans = [pairc[pair] for pair in pairs]

print(*ans)

Submission status: Accepted

Solution code:
#解説、答え参照済み
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n #各要素の親要素の番号を格納するリスト

    def find(self, x): #要素xが属するグループの根を返す
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]

    def union(self,x,y): #要素xが属するグループと要素yが属するグループとを併合する
        x=self.find(x)
        y=self.find(y)

        if x==y:
            return

        if self.parents[x]>self.parents[y]:
            x,y=y,x

        self.parents[x]+=self.parents[y]
        self.parents[y]=x

    def size(self,x): #要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self,x,y): #要素x, yが同じグループに属するかどうかを返す
        return self.find(x)==self.find(y)

    def members(self,x): #要素xが属するグループに属する要素をリストで返す
        root=self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]

    def roots(self): #すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x<0]

    def group_count(self): #グループの数を返す
        return len(self.roots())

    def all_group_members(self): #{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

#print(list(uf.all_group_members().values())) #グループ一覧を表示

def main():
    n,k,l=map(int,input().split())
    ufr=UnionFind(n)
    uft=UnionFind(n)
    for i in range(k):
        x,y=map(int,input().split())
        ufr.union(x-1,y-1)
    for i in range(l):
        x,y=map(int,input().split())
        uft.union(x-1,y-1)
    
    pairs = [(ufr.find(i), uft.find(i)) for i in range(n)]
    from collections import Counter
    pairs_counter = Counter(pairs)
    ans = [pairs_counter[pair] for pair in pairs]
    print(*ans)

if __name__=="__main__" :
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


class UnionFind:
    def __init__(self, n: int):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x: int):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        if self.parents[y] < self.parents[x]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x: int):
        return -self.parents[self.find(x)]
    
    def same(self, x: int, y: int):
        return self.find(x) == self.find(y)
    
    def members(self, x: int):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def solve():
    N, K, L = map(int, input().split())
    connect_road, connect_rail = UnionFind(N), UnionFind(N)
    for _ in range(K):
        p, q = map(lambda x: int(x) - 1, input().split())
        connect_road.union(p, q)
    for _ in range(L):
        r, s = map(lambda x: int(x) - 1, input().split())
        connect_rail.union(r, s)
    
    root = defaultdict(int)
    for i in range(N):
        root[(connect_road.find(i), connect_rail.find(i))] += 1
    for i in range(N):
        print(root[(connect_road.find(i), connect_rail.find(i))])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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-1, q-1)
for _ in range(L):
    r, s = map(int, input().split())
    uf2.union(r-1, s-1)

pairs = [(uf1.find(i), uf2.find(i)) for i in range(N)]
from collections import Counter
pairs_counter = Counter(pairs)
ans = [pairs_counter[pair] for pair in pairs]
print(*ans)