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
from collections import defaultdict

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

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

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

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

def main():
    input = sys.stdin.readline
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    rail = UnionFind(N)

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

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

    d = defaultdict(lambda: 0)
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)
        d[(n, m)] += 1

    ans = []
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)
        ans.append(d[(n, m)])

    return print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from fractions import gcd
#from math import factorial
from math import sqrt
from math import ceil
from itertools import permutations
from heapq import *
class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.size_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.size_)

    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):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_


N,K,L=map(int,input().split())
inf1=[]
for _ in range(K):
    inf1.append(list(map(int,input().split())))
inf2=[]
for _ in range(L):
    inf2.append(list(map(int,input().split())))
U=[UnionFindNode(i) for i in range(N+1)]
for i in range(K):
    x=inf1[i][0]
    y=inf1[i][1]
    U[x].unite(U[y])
U_=[UnionFindNode(i) for i in range(N+1)]
for i in range(L):
    x=inf2[i][0]
    y=inf2[i][1]
    U_[x].unite(U_[y])
d=defaultdict(int)
for i in range(1,N+1):
    k=(U[i].find(),U_[i].find())
    d[k]+=1
ans=[]
for i in range(1,N+1):
    k=(U[i].find(),U_[i].find())
    ans.append(d[k])
print(" ".join(map(str,ans)))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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)

N, K, L = MAP()

tree_pq = UnionFind(N+1) # N点集合からUnionFind木を作成
tree_rs = UnionFind(N+1)
pq = [LIST() for _ in range(K)]
for p, q in pq:
	tree_pq.union(p, q) # p, qを同じグループに
group_pq = [tree_pq.find(i) for i in range(N+1)]
# print(group_pq)
rs = [LIST() for _ in range(L)]
for r, s in rs:
	tree_rs.union(r, s)
group_rs = [tree_rs.find(i) for i in range(N+1)]
# print(group_rs)

keys = []
dic = {}
pairs = [(group_pq[i], group_rs[i]) for i in range(N+1)]
for i in range(1, N+1):
	pair = (group_pq[i], group_rs[i])
	keys.append(pair)
	if pair in dic:
		dic[pair] += 1
	else:
		dic[pair] = 1

ans = [str(dic[key]) for key in keys]
print(" ".join(ans))

Submission status: Accepted

Solution code:
n, k, l = map(int, input().split())
load = [-1] * (n + 1)
train = [-1] * (n + 1)

def find_load(x, u = load):
    if u[x] < 0 :
        return x
    else:
        u[x] = find_load(u[x])
        return u[x]

def find_train(x, u = train):
    if u[x] < 0 :
        return x
    else:
        u[x] = find_train(u[x])
        return u[x]

for i in range(k):

    p, q = map(int, input().split())
    p, q = map(find_load, [p, q])
    p, q = sorted((p, q))
    if p != q:
        load[q] = p

load = [i if x < 0 else x for i, x in enumerate(load)]

for i in range(l):
    r, s = map(int, input().split())
    r, s = map(find_train, [r, s])
    r, s = sorted((r, s))
    if r != s:
        train[s] = r
train = [i if x < 0 else x for i, x in enumerate(train)]

keys = []
dic  = {}

for node in range(n):
    key = (find_load(load[node + 1]), find_train(train[node + 1]))
    keys.append(key)
    if key in dic:
        dic[key] += 1
    else:
        dic[key] = 1

ans = [str(dic[key]) for key in keys]
print(" ".join(ans))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size: int):
        self.__size = size
        self.__root = [-1] * size

    def root(self, x: int)->int:
        if self.__root[x] < 0:
            return x
        self.__root[x] = self.root(self.__root[x])
        return self.__root[x]

    def size(self, x: int)->int:
        root = self.root(x)
        return self.__root[root]

    def same(self, x: int, y: int)->bool:
        return self.root(x) == self.root(y)

    def unite(self, x: int, y: int):
        rx, ry = self.root(x), self.root(y)

        if rx == ry:
            return

        if ry < rx:
            rx, ry = ry, rx

        self.__root[rx] += self.__root[ry]
        self.__root[ry] = rx


def connectivity(N: int, K: int, L: int, roads: list, rails: list)->list:
    road_uf, rail_uf = UnionFind(N), UnionFind(N)

    for p, q in roads:
        road_uf.unite(p-1, q-1)

    for r, s in rails:
        rail_uf.unite(r-1, s-1)

    freq = {}
    for i in range(N):
        p = (road_uf.root(i), rail_uf.root(i))
        freq.setdefault(p, 0)
        freq[p] += 1

    return [freq[(road_uf.root(i), rail_uf.root(i))] for i in range(N)]


if __name__ == "__main__":
    K = 0
    L = 0
    N, K, L = map(int, input().split())
    roads = [tuple(int(s) for s in input().split()) for _ in range(K)]
    rails = [tuple(int(s) for s in input().split()) for _ in range(L)]
    ans = connectivity(N, K, L, roads, rails)
    print(' '.join(map(str, ans)))

Submission status: Accepted

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

from collections import Counter

class Unionfind:

    __slots__ = ['nodes','size']

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

    def root(self, x):
        if self.nodes[x] == x:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.nodes[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.size[x] < self.size[y]:
            x, y = y, x
        self.size[x] += self.size[y]
        self.nodes[y] = x

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

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

uf1 = Unionfind(N)
uf2 = Unionfind(N)

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

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

# 方針 :各nodeについて(r1,r2)を求める
# dicで(r1,r2)となるようなnodeを数える

keys = []
dic = Counter()

for node in range(N):
    key = (uf1.root(node),uf2.root(node))
    keys.append(key)
    dic[key] += 1

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

Submission status: Accepted

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

class Unionfind:

    __slots__ = ['nodes','size']

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

    def root(self, x):
        if self.nodes[x] == x:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.nodes[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.size[x] < self.size[y]:
            x, y = y, x
        self.size[x] += self.size[y]
        self.nodes[y] = x

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

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

uf1 = Unionfind(N)
uf2 = Unionfind(N)

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

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

keys = []
dic = {}

for node in range(N):
    key = (uf1.root(node),uf2.root(node))
    keys.append(key)
    if key in dic:
        dic[key] += 1
    else:
        dic[key] = 1

ans = [str(dic[key]) for key in keys]
print(" ".join(ans))

Submission status: Accepted

Solution code:
import collections


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

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

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

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


N, K, L = map(int, input().split())
graph_road = UnionFind(N)
graph_train = UnionFind(N)
for k in range(K):
    p, q = map(int, input().split())
    graph_road.unite(p-1, q-1)

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

pair = collections.defaultdict(int)
for i in range(N):
    road = graph_road.root(i)
    train = graph_train.root(i)
    pair[(road, train)] += 1

for i in range(N):
    road = graph_road.root(i)
    train = graph_train.root(i)
    print(pair[(road, train)])

Submission status: Accepted

Solution code:
N, K, L = map(int, input().split())
pq = [map(int, input().split()) for _ in range(K)]
rs = [map(int, input().split()) for _ in range(L)]

class UnionFind:
    def __init__(self, N):
        self.par = [None] * (N+1)
        self.rank = [None] * (N+1)
        for n in range(N+1):
            self.par[n] = n
            self.rank[n] = 1

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            if self.rank[rx] > self.rank[ry]:
                self.par[ry] = rx
            else:
                self.par[rx] = ry
                if self.rank[rx] == self.rank[ry]:
                    self.rank[ry] += 1

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

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

for p, q in pq:
    uf_road.unite(p, q)
for r, s in rs:
    uf_train.unite(r, s)

from collections import Counter
c = Counter()
for i in range(1, N+1):
    k = (uf_road.root(i), uf_train.root(i))
    c[k] += 1

ret = []
for i in range(1, N+1):
    k = (uf_road.root(i), uf_train.root(i))
    ret.append(c[k])

print(" ".join(str(v) for v in ret))

Submission status: Accepted

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

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

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

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

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

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

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

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

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

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

d = {}
for i in range(n):
    x = (road.root(i), rail.root(i))
    if x not in d:
        d[x] = 0
    d[x] +=1

res = [d[(road.root(i), rail.root(i))] for i in range(n)]
print(*res)

Submission status: Accepted

Solution code:
class UnionFindTree():
    def __init__(self, values=[]):
        self.__parent_of = {}
        self.__rank_of = {}
        for value in values:
            self.add(value)

    def add(self, value):
        if value in self.__parent_of:
            raise RuntimeError("Dupulicated Value Added")
        self.__parent_of[value] = None
        self.__rank_of[value] = 0

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
            else:
                self.__parent_of[r2] = r1
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1


def main():
    N, K, L = map(int, input().split())
    uft = UnionFindTree(range(N))
    for _ in range(K):
        p, q = map(int, input().split())
        uft.unite(p-1, q-1)
    uft2 = UnionFindTree(range(N))
    for _ in range(L):
        r, s = map(int, input().split())
        uft2.unite(r-1, s-1)
    pair = [(0, 0)] * N
    cnt = {}
    for i in range(N):
        p = (uft.root(i), uft2.root(i))
        if p not in cnt:
            cnt[p] = 0
        cnt[p] += 1
        pair[i] = p
    ans = [0] * N
    for i in range(N):
        ans[i] = cnt[pair[i]]
    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def root(x,d):
    if d[x]!=x:
        d[x]=root(d[x],d)
    return d[x]
def unite(x,y,h):
    x=root(x,h)
    y=root(y,h)
    if x!=y:
        h[x]=min(x,y)
        h[y]=h[x]
from collections import defaultdict
n,k,l=map(int,input().split())
a=[i for i in range(n+1)]
b=[i for i in range(n+1)]
for i in range(k):
    s,t=map(int,input().split())
    unite(s,t,a)
for i in range(l):
    s,t=map(int,input().split())
    unite(s,t,b)
d=defaultdict(int)
l=""
for i in range(1,n+1):
    d[(root(a[i],a),root(b[i],b))]+=1
for i in range(1,n+1):
    l+=str(d[(root(a[i],a),root(b[i],b))])+" "
print(l[:-1])

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
    def find(self, x):
        if self.par[x] == x:
          return x
        else:
          self.par[x] = self.find(self.par[x])
          return self.find(self.par[x])
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

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

for i in range(k):
  x, y = map(int, input().split())
  uf1.union(x-1, y-1)
for i in range(l):
  x, y = map(int, input().split())
  uf2.union(x-1, y-1)

pair = [(uf1.find(i), uf2.find(i)) for i in range(n)]
import collections
c = collections.Counter(pair)
ans = [c[pair[i]] for i in range(n)]

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

Submission status: Accepted

Solution code:
from collections import Counter

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

    def find_root(self, x):
        if self.p[x] != x:
            self.p[x] = self.find_root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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


n, K, L = map(int, input().split())
pq = [tuple(int(x)-1 for x in input().split()) for _ in range(K)]
rs = [tuple(int(x)-1 for x in input().split()) for _ in range(L)]

uk = UnionFind(n)
for p, q in pq:
    uk.unite(p, q)

ul = UnionFind(n)
for p, q in rs:
    ul.unite(p, q)

res = [uk.find_root(i) * 1000000 +  ul.find_root(i) for i in range(n)]
c = Counter(res)
ans = [0] * n

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

print(*ans, sep=' ')

Submission status: Accepted

Solution code:
from collections import defaultdict


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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

        if x == y:
            return

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

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


D = defaultdict(int)
n,k,l =  map(int, input().split())
uf = UnionFind(n)
tf = UnionFind(n)

dp =[1]*n
for i in range(k):
    x,y =map(int, input().split())
    uf.union(x-1, y-1)  # (3)
for i in range(l):
    x,y =map(int, input().split())
    tf.union(x-1, y-1)  # (3)
tf.all_find()
uf.all_find()
D = defaultdict(int)
for r, t in zip(uf.par, tf.par):
    D[(r, t)] += 1
 
ans = [D[(r, t)] for r, t in zip(uf.par, tf.par)]
print(*ans, sep=' ')

Submission status: Accepted

Solution code:
from collections import Counter
N, K, L = [int(i) for i in input().split()]
par = [i for i in range(N)]
rank = [1 for i in range(N)]

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

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        pass
    else:
        if rank[x] > rank[y]:
            par[y] = x
            rank[x] += rank[y]
        else:
            par[x] = par[y]
            rank[y] += rank[x]


def find_2(x):
    if par_2[x] == x:
        return x
    else:
        return find_2(par_2[x])

def unite_2(x, y, is_incre=True):
    x = find_2(x)
    y = find_2(y)
    if x == y:
        pass
    else:
        if rank_2[x] > rank_2[y]:
            par_2[y] = x
            if is_incre:
                rank_2[x] += rank_2[y]
        else:
            par_2[x] = par_2[y]
            if is_incre:
                rank_2[y] += rank_2[x]

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

def is_same_2(x, y):
    if find_2(x) == find_2(y):
        return True
    else:
        return False

for i in range(K):
    p, q = [int(i)-1 for i in input().split()]
    if is_same(p, q):
        continue
    else:
        unite(p, q)

rank_2 = [1 for i in range(N)]
par_2 = [i for i in range(N)]
for l in range(L):
    r, s = [int(i)-1 for i in input().split()]
    if is_same_2(r, s):
        pass
    else:
        unite_2(r, s)

par_ls = list()
for i in range(N):
    ar = find(i)
    br = find_2(i)
    par_ls.append((ar, br))
ct = Counter(par_ls)

for i in range(N):
    print(ct[par_ls[i]])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N,K,L=map(int,input().split())
road=[tuple(map(int,input().split())) for _ in range(K)]
metro=[tuple(map(int,input().split())) for _ in range(L)]
inf=float('inf')
def Find(root,x):
    if root[x]<0:
        return x
    if root[x]>=0:
        root[x]=Find(root,root[x])
        return root[x]

def UnionFind(N,branch):
    root=[-1]*(N+1)
    for a,b in branch:
        aroot=Find(root,a)
        broot=Find(root,b)
        if aroot==broot:continue
        elif root[aroot]<=root[broot]:
            root[aroot]+=root[broot]
            root[broot]=aroot
        elif root[aroot]>root[broot]:
            root[broot]+=root[aroot]
            root[aroot]=broot
    return root
r_root=UnionFind(N,road)
m_root=UnionFind(N,metro)
from collections import defaultdict
data=[]
cnt=defaultdict(int)
for i in range(1,N+1):
    ri=Find(r_root,i)
    mi=Find(m_root,i)
    data.append((ri,mi))
    cnt[(ri,mi)]+=1
ans=''
for d in data:
    ans+=str(cnt[d])+' '
print(ans[:-1])

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,N):
        self.table = [i for i in range(N)]
        self.size = [1] * N
        self.rank = [0] * N
    
    def find(self,x):
        if self.table[x] == x:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]
    
    def unite(self,x,y):
        x,y = self.find(x),self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.table[x] = y
            self.size[y] += self.size[x]
        else:
            self.table[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same(self,x,y):
        return self.table[x] == self.table[y]

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

N,K,L = map(int,input().split())
uf_road = UnionFind(N)
uf_rail = UnionFind(N)
for k in range(K):
    p,q = map(int,input().split())
    uf_road.unite(p-1,q-1)
for l in range(L):
    r,s = map(int,input().split())
    uf_rail.unite(r-1,s-1)

d = {}
for i in range(N):
    k = (uf_road.find(i),uf_rail.find(i))
    if k in d.keys():
        d[k] += 1
    else:
        d[k] = 1

ans = []
for i in range(N):
    k = (uf_road.find(i),uf_rail.find(i))
    ans.append(d[k])
print(*ans)

Submission status: Accepted

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

from collections import Counter

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

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

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

#for i in range(n):
#uf1.find(i)
#uf2.find(i)

ctr=Counter()
for i in range(n):
    r1 = uf1.find(i)
    r2 = uf2.find(i)
    ctr[(r1,r2)]+=1

ans=[]
for i in range(n):
    r1 = uf1.find(i)
    r2 = uf2.find(i)
    ans.append(ctr[(r1,r2)])
print(*ans)

Submission status: Accepted

Solution code:
import sys

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

def unite(x,y,par,rank): 
    x = find(x,par,rank)
    y = find(y,par,rank)
    if (x != y):
        if rank[x] < rank[y]:
            par[x] = y
        else :
            par[y] = x
            if (rank[x] == rank[y]) : rank[x] += 1

def same(x,y,par,rank):
    return (find(x,par,rank) == find(y,par,rank)) 

n,k,l = map(int, sys.stdin.readline().split())

par1 = [i for i in range(n)]
par2 = [i for i in range(n)]
rank1 = [0 for i in range(n)]
rank2 = [0 for i in range(n)]

for i in range(k):
    pp,qq = map(int, sys.stdin.readline().split())
    unite(pp-1,qq-1,par1,rank1)

for i in range(l):
    rr,ss = map(int, sys.stdin.readline().split())
    unite(rr-1,ss-1,par2,rank2)

dic = {}
parlis = []
for i in range(n):
    p1 = find(i,par1,rank1)
    p2 = find(i,par2,rank2)
    parlis.append((p1,p2))
    if (p1,p2) in dic:
        dic[(p1,p2)] += 1
    else: 
        dic[(p1,p2)] = 1

ans =[]

for i in range(n):
    ans.append(dic[parlis[i]])

print(*ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
s = input()
while s:
    if s[:11] == "dreameraser":
        s = s[11:]
    elif s[:10] == "dreamerase":
        s = s[10:]
    elif s[:7] == "dreamer":
        s = s[7:]
    elif s[:6] == "eraser":
        s = s[6:]
    elif s[:5] == "dream":
        s = s[5:]
    elif s[:5] == "erase":
        s = s[5:]
    else:
        print("NO")
        quit()
print("YES")
"""

#D
def root(x,par,rank):
    if x == par[x]:
        return x
    par[x] = root(par[x],par,rank)
    return par[x]
def unite(x,y,par,rank):
    x = root(x,par,rank)
    y = root(y,par,rank)
    if x == y:return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
n,k,l = LI()
par1 = [i for i in range(n)]
rank1 = [0 for i in range(n)]
par2 = [i for i in range(n)]
rank2 = [0 for i in range(n)]
for i in range(k):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par1,rank1)
for i in range(l):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par2,rank2)
d = {}
for i in range(n):
    k = (root(i,par1,rank1),root(i,par2,rank2))
    if k in d:
        d[k] += 1
    else:
        d[k] = 1
ans = []
for i in range(n):
    k = (root(i,par1,rank1),root(i,par2,rank2))
    ans.append(d[k])
print(*ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T