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:
import sys
input = sys.stdin.readline
class UnionFindNode:
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1
        self.member_num_ = 1

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                n_root, child = root, unite_root
            else:
                n_root, child = unite_root, root
            child.parent_ = n_root
            n_root.rank_ = max(n_root.rank_, child.rank_ + 1)
            n_root.member_num_ = n_root.member_num_ + child.member_num_
N, K, L = map(int, input().split())
node_list1 = [UnionFindNode(i) for i in range(N)]
node_list3 = [UnionFindNode(i) for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    node_list1[a-1].unite(node_list1[b-1])
#    node_list3[a-1].unite(node_list3[b-1])
    
node_list2 = [UnionFindNode(i) for i in range(N)]
for _ in range(L):
    a, b = map(int, input().split())
    node_list2[a-1].unite(node_list2[b-1])
#    node_list3[a-1].unite(node_list3[b-1])
rs = []
from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    rs.append((node_list1[i].root().group_id_, node_list2[i].root().group_id_))
    d[(node_list1[i].root().group_id_, node_list2[i].root().group_id_)] += 1

for i in range(N):
    print(d[(node_list1[i].root().group_id_, node_list2[i].root().group_id_)])

Submission status: Accepted

Solution code:
# AtCoder Regular Contest 065
# D - 連結 / Connectivity
# https://atcoder.jp/contests/arc065/tasks/arc065_b
import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
    def find(self, x):
        if self.parent[x] == x:
            return 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
        self.parent[x] = y

def main():
    N, *KL = map(int, input().split())
    uf = [UnionFind(N) for _ in range(2)]
    for i in range(2):
        for j in range(KL[i]):
            p, q = map(int, input().split())
            uf[i].union(p-1, q-1)

    d = defaultdict(int)
    for i in range(N):
        d[(uf[0].find(i), uf[1].find(i))] += 1

    print(*[d[(uf[0].find(i), uf[1].find(i))] for i in range(N)])

if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    main()

Submission status: Accepted

Solution code:
# AtCoder Regular Contest 065
# D - 連結 / Connectivity
# https://atcoder.jp/contests/arc065/tasks/arc065_b
import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        # self.parent = [i for i in range(n)]
        self.parent = list(range(n))
    def find(self, x):
        if self.parent[x] == x:
            return 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
        self.parent[x] = y

def main():
    N, *KL = map(int, input().split())
    uf = [UnionFind(N) for _ in range(2)]
    for i in range(2):
        for j in range(KL[i]):
            p, q = map(int, input().split())
            uf[i].union(p-1, q-1)

    d = defaultdict(int)
    for i in range(N):
        d[(uf[0].find(i), uf[1].find(i))] += 1

    print(*[d[(uf[0].find(i), uf[1].find(i))] for i in range(N)])
    # for i in range(N):
    #     print(d[(uf[0].find(i), uf[1].find(i))], end = " ")
    # print("")
    
    #print(" ".join([str(d[(uf[0].find(i), uf[1].find(i))]) for i in range(N)]))

if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    main()

Submission status: Accepted

Solution code:
# AtCoder Regular Contest 065
# D - 連結 / Connectivity
# https://atcoder.jp/contests/arc065/tasks/arc065_b
import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        # self.parent = [i for i in range(n)]
        self.parent = list(range(n))
    def find(self, x):
        if self.parent[x] == x:
            return 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
        self.parent[x] = y

def main():
    N, *KL = map(int, input().split())
    uf = [UnionFind(N) for _ in range(2)]
    for i in range(2):
        for j in range(KL[i]):
            p, q = map(int, input().split())
            uf[i].union(p-1, q-1)

    d = defaultdict(int)
    for i in range(N):
        d[(uf[0].find(i), uf[1].find(i))] += 1

    ans = [d[(uf[0].find(i), uf[1].find(i))] for i in range(N)]
    print(*ans)
    # for i in range(N):
    #     print(d[(uf[0].find(i), uf[1].find(i))], end = " ")
    # print("")
    
    #print(" ".join([str(d[(uf[0].find(i), uf[1].find(i))]) for i in range(N)]))

if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    main()

Submission status: Accepted

Solution code:
# AtCoder Regular Contest 065
# D - 連結 / Connectivity
# https://atcoder.jp/contests/arc065/tasks/arc065_b
import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        # self.parent = [i for i in range(n)]
        self.parent = list(range(n))
    def find(self, x):
        if self.parent[x] == x:
            return 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
        self.parent[x] = y

def main():
    N, *KL = map(int, input().split())
    uf = [UnionFind(N) for _ in range(2)]
    for i in range(2):
        for j in range(KL[i]):
            p, q = map(int, input().split())
            uf[i].union(p-1, q-1)

    d = defaultdict(int)
    for i in range(N):
        d[(uf[0].find(i), uf[1].find(i))] += 1

    # for i in range(N):
    #     print(d[(uf[0].find(i), uf[1].find(i))], end = " ")
    # print("")
    
    print(" ".join([str(d[(uf[0].find(i), uf[1].find(i))]) for i in range(N)]))

if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

class Unionfind:

    __slots__ = ['parents','sizes']

    def __init__(self, n):
        self.parents = list(range(n))
        self.sizes = [1]*n

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

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.sizes[x] += self.sizes[y]
        self.parents[y] = x

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

    # 集合自体の数 ({1,2}, {3}, {4} : kind -> 3)
    def kind(self):
        for v in range(N):
            self.root(v)
        return len(list(set(self.parents)))

    # xが属する集合の要素の数　({1,2,3} : size(2) -> 3)
    def size(self, x):
        self.sizes[x] = self.sizes[self.root(x)]
        return self.sizes[x]

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

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

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

cnt = defaultdict(int)

for i in range(N):
    key = (road.root(i), train.root(i))
    cnt[key] += 1

ans_list = []
for i in range(N):
    key = (road.root(i), train.root(i))
    ans = cnt[key]
    ans_list.append(ans)

print(*ans_list)

Submission status: Accepted

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

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 main():
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    train = UnionFind(N)
    for _ in range(K):
        p, q = map(int, input().split())
        p -= 1
        q -= 1
        road.union(p,q)
    for _ in range(L):
        r, s = map(int, input().split())
        r -= 1
        s -= 1
        train.union(r,s)

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

    ans = [0] * N

    for i in range(N):
        a = road.find(i)
        b = train.find(i)
        ans[i] = d[(a,b)]
    print(*ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
con = 300000

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.size = [1] * (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 same_check(self, 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]:
            if self.same_check(x, y) != True:
                self.size[y] += self.size[x]
                self.size[x] = 0
            self.par[x] = y
        else:
            if self.same_check(x, y) != True:
               self.size[x] += self.size[y]
               self.size[y] = 0
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
               self.rank[x] += 1

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

#処理内容
def main():
	#受け取り、処理
	N, K, L = getlist()
	UFp = UnionFind(N)
	UFr = UnionFind(N)
	for i in range(K):
		p, q = getlist()
		UFp.union(p, q)
	for i in range(L):
		r, s = getlist()
		UFr.union(r, s)

	for i in range(1, N):
		UFp.find(i)
		UFr.find(i)

	s1 = UFp.par
	s2 = UFr.par
	s3 = []
	
	for i in range(1, N + 1):
		s3.append([s1[i], s2[i]])

	#前計算
	D = defaultdict(int)
	for i in range(N):
		a = s3[i][0]
		b = s3[i][1]
		D[a * con + b] += 1
	#答え
	ans = []
	for i in range(N):
		ans.append(D[s3[i][0] * con + s3[i][1]])
	print(" ".join(list(map(str, ans))))

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import defaultdict

class UnionFind :
    def __init__(self, size) :
        """
        Parameters
        ---
        size : int
            頂点数
        """
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        """
        親のインデックスの取得

        Parameters
        ---
        index : int
            取得する頂点のインデックス

        Returns
        ---
        rootIndex : int
            指定した頂点の根のインデックス
        """
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        """
        木の結合

        Parameters
        ---
        index1 : int
        index2 : int
            結合する頂点のインデックス
        """
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        """
        同じ木に属するかを判定する

        Parameters
        ---
        index1 : int
        index2 : int

        Returns
        ---
        boolean
        """
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        """
        指定した頂点の属する木の大きさを取得する
        """
        return self.size[self.root(index)]

    def getComponent(self) :
        """
        連結成分数を取得する
        """
        return self.component

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

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

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

for _ in range(L):
    p, q = map(int, input().split())
    train.union(p - 1, q - 1)

cnt = defaultdict(int)

for i in range(N):
    cnt[(road.root(i), train.root(i))] += 1

ans = []
for i in range(N):
    ans.append(cnt[(road.root(i), train.root(i))])

print(*ans)

Submission status: Accepted

Solution code:
N,K,L = map(int,input().split())
PQ = [tuple(map(int,input().split())) for i in range(K)]
RS = [tuple(map(int,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

roads = UnionFind(N)
rails = UnionFind(N)
for p,q in PQ:
    p,q = p-1,q-1
    roads.unite(p,q)
for r,s in RS:
    r,s = r-1,s-1
    rails.unite(r,s)
for i in range(N):
    roads.root(i)
    rails.root(i)

from collections import Counter
ctr = Counter()
for i in range(N):
    ctr[(roads.parent[i], rails.parent[i])] += 1
ans = []
for i in range(N):
    ans.append(ctr[(roads.parent[i], rails.parent[i])])
print(*ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

road = [tuple(map(int,input().split())) for i in range(K)]
train = [tuple(map(int,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 p,q in road:
    p,q = p-1, q-1
    if not uf_road.is_same(p,q):
        uf_road.unite(p,q)

uf_train = UnionFind(N)
for r,s in train:
    r,s = r-1, s-1
    if not uf_train.is_same(r,s):
        uf_train.unite(r,s)

total_union_num = Counter()
for i in range(N):
    r = uf_road.root(i)
    t = uf_train.root(i)
    total_union_num[(r,t)] += 1

ans = []
for i in range(N):
    r = uf_road.root(i)
    t = uf_train.root(i)
    ans.append(total_union_num[(r,t)])

print(*ans)

Submission status: Accepted

Solution code:
class UnionFind :
    """
    Union Find木
    ---
    頂点のインデックスは0~

    Attributes
    ---
    parent : list<int>
        親のリスト．parent[頂点のインデックス] = 親のインデックス
    height : list<int>
        各木の高さ
    size : list<int>
        各木の頂点数
    component : int
        連結成分の数
    """

    def __init__(self, size) :
        """
        Parameters
        ---
        size : int
            頂点数
        """
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        """
        親のインデックスの取得

        Parameters
        ---
        index : int
            取得する頂点のインデックス

        Returns
        ---
        rootIndex : int
            指定した頂点の根のインデックス
        """
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        """
        木の結合

        Parameters
        ---
        index1 : int
        index2 : int
            結合する頂点のインデックス
        """
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        root1, root2 = min(root1, root2), max(root1, root2)
        self.parent[root2] = root1


    def isSameRoot(self, index1, index2) :
        """
        同じ木に属するかを判定する

        Parameters
        ---
        index1 : int
        index2 : int

        Returns
        ---
        boolean
        """
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        """
        指定した頂点の属する木の大きさを取得する
        """
        return self.size[self.root(index)]

    def getComponent(self) :
        """
        連結成分数を取得する
        """
        return self.component

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

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

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

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

countList = []
for i in range(N):
    countList.append((train.root(i), road.root(i)))

count = Counter(countList)
ans = [count[(train.root(i), road.root(i))] for i in range(N)]
print(*ans)

Submission status: Accepted

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


class UnionFind(object):
    '''Represents a data structure that tracks a set of elements partitioned
       into a number of disjoint (non-overlapping) subsets.
    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.
    See:
    https://www.youtube.com/watch?v=zV3Ul2pA2Fw
    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
    https://atcoder.jp/contests/abc120/submissions/4444942
    '''

    def __init__(self, number_count: int):
        '''
        Args:
            number_count: The size of elements (greater than 2).
        '''
        self.parent_numbers = [-1 for _ in range(number_count)]

    def find_root(self, number: int) -> int:
        '''Follows the chain of parent pointers from number up the tree until
           it reaches a root element, whose parent is itself.
        Args:
            number: The trees id (0-index).
        Returns:
            The index of a root element.
        '''
        if self.parent_numbers[number] < 0:
            return number

        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])
        return self.parent_numbers[number]

    def get_group_size(self, number: int) -> int:
        '''
        Args:
            number: The trees id (0-index).
        Returns:
            The size of group.
        '''
        return -self.parent_numbers[self.find_root(number)]

    def is_same_group(self, number_x: int, number_y: int) -> bool:
        '''Represents the roots of tree number_x and number_y are in the same
           group.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        return self.find_root(number_x) == self.find_root(number_y)

    def merge_if_needs(self, number_x: int, number_y: int) -> bool:
        '''Uses find_root to determine the roots of the tree number_x and
           number_y belong to. If the roots are distinct, the trees are combined
           by attaching the roots of one to the root of the other.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        x = self.find_root(number_x)
        y = self.find_root(number_y)

        if x == y:
            return False

        if self.get_group_size(x) >= self.get_group_size(y):
            self.parent_numbers[x] += self.parent_numbers[y]
            self.parent_numbers[y] = x
        else:
            self.parent_numbers[y] += self.parent_numbers[x]
            self.parent_numbers[x] = y
        return True


def main():
    from collections import Counter

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

    for _ in range(k):
        pi, qi = map(lambda x: int(x) - 1, input().split())

        if road.is_same_group(pi, qi):
            continue

        road.merge_if_needs(pi, qi)

    for _ in range(l):
        ri, si = map(lambda x: int(x) - 1, input().split())

        if rail.is_same_group(ri, si):
            continue

        rail.merge_if_needs(ri, si)

    # See:
    # https://atcoder.jp/contests/arc065/submissions/3559412
    # http://tutuz.hateblo.jp/entry/2018/07/25/225115
    # http://baitop.hatenadiary.jp/entry/2018/06/26/224712
    pairs = Counter()
    ans = [0 for _ in range(n)]

    for i in range(n):
        hwy = road.find_root(i)
        rwy = rail.find_root(i)
        pairs[(hwy, rwy)] += 1

    for i in range(n):
        hwy = road.find_root(i)
        rwy = rail.find_root(i)
        ans[i] = pairs[(hwy, rwy)]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections
#
# class UnionFind():
#     def __init__(self,n):
#         self.par = [i for i in range(n+1)]
#         self.rank = [0 for _ in range(n+ 1)]
#     def find(self,x):
#         if self.par[x] == x:
#             return x
#         self.par[x] = self.find(self.par[x])
#         return  self.par[x]
#
#     def same_check(self,a,b):
#             return self.find(a) == self.find(b)
#
#     def union(self,x,y):
#         if self.rank[x] > self.rank[y]:
#             self.par[y] = self.par[x]
#         else:
#             self.par[x] = self.par[y]
#             if self.rank[x] == self.rank[y]:
#                 self.rank[x] += 1

class UnionFind:
    def __init__(self, size):
        self.parent = [-1] * (size + 1)  # 非負なら親ノード，負ならグループの要素数

    def root(self, x):  # root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        elif self.parent[self.parent[x]] < 0:
            return self.parent[x]
        else:
            self.parent[x] = self.root(self.parent[x])  # xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y):  # merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]:  # xの要素数がyの要素数より「小さい」とき入れ替える
            x, y = y, x
        self.parent[x] += self.parent[y]  # xの要素数を更新
        self.parent[y] = x  # yをxにつなぐ
        return True

    def issame(self, x, y):  # same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)

    def size(self, x):  # size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]


def do():
    sys.setrecursionlimit(100000000)

    N,K,L = list(map(int, input().split(" ")))
    querys1 = [list(map(int, input().split(" "))) for i in range(K)]
    querys2 = [list(map(int, input().split(" "))) for i in range(L)]
    uf1 = UnionFind(N + 1)
    uf2 = UnionFind(N + 1)
    for query in querys1:
        a,b= query
        uf1.merge(a,b)
    for query in querys2:
        a, b = query
        uf2.merge(a, b)
    di = collections.defaultdict(lambda :0)
    for i in range(1,N+1):
        di[ (uf1.root(i),uf2.root(i))] += 1
    anss = []
    for i in range(1,N+1):

        anss.append( str(di[(uf1.root(i),uf2.root(i))]))
    print(" ".join(anss))

if __name__ == "__main__":
    do()

Submission status: Accepted

Solution code:
N,K,L=map(int,input().split())
pq=[list(map(int,input().split())) for i in range(K)]
rs=[list(map(int,input().split())) for i in range(L)]
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
u=UnionFind(N)
v=UnionFind(N)
for e in pq:
    u.unite(e[0]-1,e[1]-1)
for e in rs:
    v.unite(e[0]-1,e[1]-1)
from collections import defaultdict
d=defaultdict(int)
for i in range(N):
    d[(u.root(i),v.root(i))]+=1
a=[]
for i in range(N):
    a.append(d[(u.root(i),v.root(i))])
print(*a)

Submission status: Accepted

Solution code:
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (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])
  
    # 結合(unite)する関数
    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[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    # 同じグループに属するかを判定する関数
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    # 要素が属する木の深さを返す関数
    def get_depth(self, x):
        return self.rank[self.find(x)]
    
    # 要素が属する木のサイズを返す関数
    def get_size(self, x):
        return self.size[self.find(x)]
    
    # グループ数を返す関数
    def group_sum(self):
        c = 0
        for i in range(len(self.par)):
            if self.find(i) == i:
                c += 1
        return c

if __name__ == "__main__":
    N,K,L = map(int, input().split())
    uf_r = UnionFind(N)
    uf_t = UnionFind(N)
    d = defaultdict(int)

    for i in range(K):
        p, q = [int(i) for i in input().split()]
        uf_r.unite(p, q)
    
    for i in range(L):
        r, s = [int(i) for i in input().split()]
        uf_t.unite(r, s)
    
    for i in range(1,N+1):
        d[(uf_r.find(i), uf_t.find(i))] += 1
    
    print(*[d[(uf_r.find(i), uf_t.find(i))] for i in range(1,N+1)])

Submission status: Accepted

Solution code:
class UnionFind():
    n=1
    rnk=[0]
    par=[0]
    sze=[1]
    def __init__(self,N):
        self.n=N
        self.rnk=[0 for i in range(self.n)]
        self.par=[i for i in range(self.n)]
        self.sze=[1 for i in range(self.n)]
    def find(self,x):
        if x==self.par[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.rnk[x]<self.rnk[y]):
            self.par[x]=y
            self.sze[y]+=self.sze[x]
            self.sze[x]=0
        else:
            self.par[y]=x
            self.sze[x]+=self.sze[y]
            self.sze[y]=0
        if (self.rnk[x]==self.rnk[y]):
            self.rnk[x]+=1
    def same(self,x,y):
        return self.find(x)==self.find(y)
    def size(self,x):
        return self.sze[self.find(x)]

N,K,L=map(int,input().split())
Train=UnionFind(N)
for i in range(K):
    p,q=map(int,input().split())
    Train.unite(p-1,q-1)
Road=UnionFind(N)
for i in range(L):
    r,s=map(int,input().split())
    Road.unite(r-1,s-1)
D=dict()
for i in range(N):
    x=Train.find(i)
    y=Road.find(i)
    if (x,y) in D:
        D[(x,y)]+=1
    else:
        D[(x,y)]=1
ans=[D[(Train.find(i),Road.find(i))] for i in range(N)]
print(" ".join([str(i) for i in ans]))