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:
# -*- coding: utf-8 -*-
"""
D - 連結 / Connectivity
https://atcoder.jp/contests/abc049/tasks/arc065_b

"""
import sys


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

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.size[self.p[x]] += self.size[self.p[y]]
            self.p[y] = self.findSet(x)
        else:
            self.size[self.p[y]] += self.size[self.p[x]]
            self.p[x] = self.findSet(y)
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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


from collections import Counter

def solve(N, K, L, PQ, RS):
    r_d = DisjointSet(N+1)
    for p, q in PQ:
        r_d.unite(p, q)
    t_d = DisjointSet(N+1)
    for r, s in RS:
        t_d.unite(r, s)
    for i in range(1, N+1):
        r_d.findSet(i)
        t_d.findSet(i)

    connectivity = Counter()
    for i in range(1, N+1):
        connectivity[(r_d.p[i], t_d.p[i])] += 1
    return [connectivity[(r_d.p[i], t_d.p[i])] for i in range(1, N + 1)]


def main(args):
    N, K, L = map(int, input().split())
    PQ = [[int(i) for i in input().split()] for _ in range(K)]
    RS = [[int(i) for i in input().split()] for _ in range(L)]
    ans = solve(N, K, L, PQ, RS)
    print(*ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
D - 連結 / Connectivity
https://atcoder.jp/contests/abc049/tasks/arc065_b

"""
import sys


class DisjointSet:
    def __init__(self, n):
        self.p = list(range(n))

    def root(self, i):
        if self.p[i] == i:
            return i
        else:
            self.p[i] = self.root(self.p[i])
            return self.p[i]

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

    def unite(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if j >= i:
            self.p[j] = i
        else:
            self.p[i] = j


from collections import Counter

def solve(N, K, L, PQ, RS):
    r_d = DisjointSet(N+1)
    for p, q in PQ:
        r_d.unite(p, q)
    t_d = DisjointSet(N+1)
    for r, s in RS:
        t_d.unite(r, s)
    for i in range(1, N+1):
        r_d.root(i)
        t_d.root(i)

    connectivity = Counter()
    for i in range(1, N+1):
        connectivity[(r_d.p[i], t_d.p[i])] += 1
    return [connectivity[(r_d.p[i], t_d.p[i])] for i in range(1, N + 1)]


def main(args):
    N, K, L = map(int, input().split())
    PQ = [[int(i) for i in input().split()] for _ in range(K)]
    RS = [[int(i) for i in input().split()] for _ in range(L)]
    ans = solve(N, K, L, PQ, RS)
    print(*ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

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

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

    def unite(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if self.rank[ru] < self.rank[rv]:
            self.par[ru] = rv
        else:
            self.par[rv] = ru
            if self.rank[ru] == self.rank[rv]:
                self.rank[ru] += 1

    def same(self, u, v):
        return self.root(u) == self.root(v)


u_road = UnionFind(N)
u_train = UnionFind(N)

for i in range(K):
    p, q = map(int, input().split())
    u_road.unite(p, q)
for i in range(L):
    r, s = map(int, input().split())
    u_train.unite(r, s)

mem = [set() for _ in range(N)]
mem_dict = dict()
for i in range(N):
    a = (u_road.root(i+1), u_train.root(i+1))
    mem[i] = a
    if a in mem_dict:
        mem_dict[a] += 1
    else:
        mem_dict[a] = 1

for i in range(N):
    print(mem_dict[mem[i]], end=' ')

print()

Submission status: Accepted

Solution code:
import collections
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
 
    def root(self, i):
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.root(self.parent[i])
            return self.parent[i]
    
    def find(self, x, y):
        return self.root(x) == self.root(y)
 
    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if j >= i:
            self.parent[j] = i
        else:
            self.parent[i] = j
N, K, L = map(int, input().split())
road = UnionFind(N)
train = UnionFind(N)
for _ in range(K):
    p, q = map(int, input().split())
    road.union(p-1, q-1)
for _ in range(L):
    r, s = map(int, input().split())
    train.union(r-1, s-1)
for i in range(N):
    road.root(i)
    train.root(i)
lst = []
for i in range(N):
    lst.append((road.parent[i], train.parent[i]))
c = collections.Counter(lst)
ans = []
for i in range(N):
    ans.append(c[lst[i]])
print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

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

PQ = [[int(x) for x in input().split()] for _ in range(K)]
RS = [[int(x) for x in input().split()] for _ in range(L)]

P,Q = zip(*PQ)
R,S = zip(*RS)

g1 = csr_matrix(([1]*K,(P,Q)),(N+1,N+1))
g2 = csr_matrix(([1]*L,(R,S)),(N+1,N+1))

_,comp1 = connected_components(g1,directed = False,return_labels = True)
_,comp2 = connected_components(g2,directed = False,return_labels = True)

comp_pair = comp1.astype('int64') * (N+1) + comp2.astype('int64')
c = Counter(comp_pair)

answer = [str(c[comp_pair[i]]) for i in range(1,N+1)]
print(' '.join(answer))

Submission status: Accepted

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

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

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            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 self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[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(int, input().split())
road = UnionFind(n)
for i in range(k):
    p, q = map(int, input().split())
    road.union(p, q)

rail = UnionFind(n)
for i in range(l):
    r, s = map(int, input().split())
    rail.union(r, s)

r = [(road.find(i + 1), rail.find(i + 1)) for i in range(n)]
c = Counter(r)
ans = []
for i in range(n):
    ans.append(c[r[i]])
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
from collections import Counter

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

sys.setrecursionlimit(10 ** 5 + 1)

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

Ut = UnionFind(n)
for i in range(l):
    r, s = map(int, input().split())
    Ut.union(r, s)

x = [(Ur.find(i + 1), Ut.find(i + 1)) for i in range(n)]
c = Counter(x)
ans = []
for i in range(n):
    ans.append(c[x[i]])
print(' '.join([str(a) for a in ans]))

Submission status: Accepted

Solution code:
from collections import defaultdict

class UnionFind:
    def __init__(self, N):
        # negative value: represents the root of a tree; its absolute value is the size of the tree
        # positive value: the parent's index
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: # v is a root
            return v
        else:
            # path compression: reconnect v to the root
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) # the root of the tree including vertex u
        s2 = self.find(v) # the root of the tree including vertex v
        
        if s1 == s2: # u and v is in the same tree
            return False
        
        if self.rank[s1] > self.rank[s2]: # the tree including u is taller
            self.vertices[s1] += self.vertices[s2] # update the size of the bigger tree
            self.vertices[s2] = s1
        else: # the tree including v is taller
            self.vertices[s2] += self.vertices[s1] # update the size of the bigger tree
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]
    
N, K, L = map(int, input().split())
uf_road = UnionFind(N)
uf_rail = UnionFind(N)
for _ in range(K):
    p, q = map(int, input().split())
    uf_road.union(p-1, q-1)
for _ in range(L):
    r, s = map(int, input().split())
    uf_rail.union(r-1, s-1)
    
d = defaultdict(int)
comp = [(uf_road.find(i), uf_rail.find(i)) for i in range(N)]
for c in comp:
    d[c] += 1
    
print(*[d[c] for c in comp], sep=' ')

Submission status: Accepted

Solution code:
import collections as cl

n,m0,m1 = map(int,input().split())

c0 = list(range(n+1))
c1 = c0[:]
a0 = []
a1 = []
for i in range(n+1):
  a0.append([i])
  a1.append([i])

for i in range(m0):
  p,q = map(int,input().split())
  s = c0[p]
  t = c0[q]
  if s == t:
    continue
  if len(a0[s]) < len(a0[t]):
    p,q = q,p
    s,t = t,s
  for x in a0[t]:
    c0[x] = s
  a0[s] += a0[t]
  a0[t] = []
  
for i in range(m1):
  p,q = map(int,input().split())
  s = c1[p]
  t = c1[q]
  if s == t:
    continue
  if len(a1[s]) < len(a1[t]):
    p,q = q,p
    s,t = t,s
  for x in a1[t]:
    c1[x] = s
  a1[s] += a1[t]
  a1[t] = []
  
c = [c0[i]*n+c1[i] for i in range(n+1)]
p = cl.Counter(c)
#print(c)
#print(p)
#quit()
ans = [str(p[c[i]]) for i in range(1,n+1)]
print(" ".join(ans))

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

def read_input():
    n, k, l = map(int, input().split())
    roads = []
    for i in range(k):
        p, q = map(int, input().split())
        roads.append((p, q))

    rails = []
    for j in range(l):
        r, s = map(int, input().split())
        rails.append((r, s))

    return n, k, l, roads, rails


def set_ids(nodes, paths):
    edge_table = {n: [] for n in nodes}

    for p in paths:
        edge_table[p[0]].append(p[1])
        edge_table[p[1]].append(p[0])

    ids = [-1] * (len(nodes) + 1)
    q = deque()
    start = 1
    group = 1
    while True:
        # まだセットしていないnodeを見つける
        while ids[start] != -1:
            start += 1
            if start > len(nodes):
                return ids

        q.appendleft(start)
        while len(q) > 0:
            curr = q.popleft()
            ids[curr] = group

            for node in edge_table[curr]:
                if ids[node] == -1:
                    q.appendleft(node)
        group += 1


def submit():
    n, k, l, roads, rails = read_input()
    nodes = list(range(1, n + 1))

    road_ids = set_ids(nodes, roads)
    rail_ids = set_ids(nodes, rails)

    count = defaultdict(int)
    for node in nodes:
        count[(road_ids[node], rail_ids[node])] += 1

    print(' '.join([str(count[(road_ids[node], rail_ids[node])]) for node in nodes]))


if __name__ == '__main__':
    submit()

Submission status: Accepted

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


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)


UF_road = UnionFind(N)
UF_train = UnionFind(N)
for k in range(K):
    p, q = map(int, input().split())
    p, q = p - 1, q - 1
    UF_road.union(p, q)
for l in range(L):
    r, s = map(int, input().split())
    r, s = r - 1, s - 1
    UF_train.union(r, s)
UF_road.all_find()
UF_train.all_find()


Count = Counter([(pr, pt) for pr, pt in zip(UF_road.par, UF_train.par)])
ans = []
for i in range(N):
    ans.append(Count[(UF_road.par[i], UF_train.par[i])])
print(*ans, sep=' ')

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.sz = [ -1 for i in range(n)]

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


    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.sz[x] > self.sz[y]:
            x,y = y,x
        self.sz[x] += self.sz[y]
        self.sz[y] = x

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

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


N,K,L = map(int,input().split())
ufpq = UnionFind(N)
ufrs = UnionFind(N)
for i in range(K):
    a,b = map(int,input().split())
    ufpq.union(a-1,b-1)
for i in range(L):
    a,b = map(int,input().split())
    ufrs.union(a-1,b-1)

pq = []
rs = []
from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    d[(ufpq.find(i),ufrs.find(i))] += 1

ans = []
for i in range(N):
    ans.append(d[(ufpq.find(i),ufrs.find(i))])
print(" ".join(map(str,ans)))

Submission status: Accepted

Solution code:
from collections import Counter

N,K,L = map(int, input().split())
pq_list = []
for _ in range(K):
    pq_list.append(list(map(int, input().split())))

rs_list = []
for _ in range(L):
    rs_list.append(list(map(int, input().split())))

class UnionFind():
    def __init__(self):
        self.roots = {}
        self.ranks = {}

    def connect(self,x,y):
        root_x = self.pick_root(x)
        root_y = self.pick_root(y)
        
#         # 経路圧縮（のつもり）
#         self.roots[x] = root_x
#         self.roots[y] = root_y
        
        if not root_x == root_y:
            if self.ranks[root_x] >= self.ranks[root_y]:
                # 短い方の根を長い方の根にする
                # 等しいときはxにくっつける
                self.roots[root_y] = root_x
            else:
                self.roots[root_x] = root_y

            if self.ranks[root_x]==self.ranks[root_y]:
                # 等しいときxにくっつけると、xのランクが1増える
                self.ranks[x] += 1

    def pick_root(self,k):
        if not k in self.roots:
            self.roots[k] = k
            self.ranks[k] = 1
            return k

        k_root = self.roots[k]
        if k_root == k:
            return k
        else:
            # pick_rootで毎回見に行くのが無駄にも思えるが、いつ根ノードがくっつくかわからないので必要な気がしている
            self.roots[k] = self.pick_root(self.roots[k_root])
            return self.roots[k]
#             return self.pick_root(k_root)

UF_pq = UnionFind()
for p,q in pq_list:
    UF_pq.connect(p, q)

UF_rs = UnionFind()
for r,s in rs_list:
    UF_rs.connect(r, s)

root_tuples = []
for i in range(1,N+1):
    # rootsにないということは、一度もconnectしてないということ
    # それであれば最終的な解答ではその街は1（自分のみ）でよいので
    # (None, None)で保存しcounterを１に変更する
    if not i in UF_pq.roots:
        root_tuples.append((None,None))
        continue
    if not i in UF_rs.roots:
        root_tuples.append((None,None))
        continue
    pq_root = UF_pq.pick_root(i)
    rs_root = UF_rs.pick_root(i)
    
    # ある都市のpqのroot,rsのrootを保存。
    # これが両方共一致する都市は、「どちらでも連結している」といえる
    root_tuples.append((pq_root,rs_root))

counter = Counter(root_tuples)
counter[(None,None)] = 1

kotae_list = []
for i in range(N):
    kotae_list.append(counter[root_tuples[i]])

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

Submission status: Accepted

Solution code:
from itertools import accumulate
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**10
from functools import reduce

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

  def union(self, a, b):
    a = self.root(a)
    b = self.root(b)
    if(a == b):
      return
    if(self.size(a) < self.size(b)):
      a, b = b, a
    self.tree[a] += self.tree[b]
    self.tree[b] = a

  def root(self, a):
    if(self.tree[a] < 0):
      return a
    res = self.root(self.tree[a])
    self.tree[a] = res
    return res

  def size(self, a):
    return -self.tree[self.root(a)]

n,k,l = map(int,input().split())
uf1 = UnionFind(n)
uf2 = UnionFind(n)
for i in range(k):
    p,q = map(int,input().split())
    p -= 1
    q -= 1
    uf1.union(p,q)
for i in range(l):
    r,s = map(int,input().split())
    r -= 1
    s -= 1
    uf2.union(r,s)
ab = [(uf1.root(i),uf2.root(i)) for i in range(n)]
c = Counter(ab)
print(" ".join(map(str,[c[i] for i in ab])))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.__data = [-1 for _ in range(size)]
    def find(self, x):
        if self.__data[x] < 0:
            return x
        else:
            self.__data[x] = self.find(self.__data[x])
            return self.__data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.__data[y] < self.__data[x]:
                x, y = y, x
            self.__data[x] += self.__data[y]
            self.__data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.__data[self.find(x)]
    def get_data(self):
        return [a if a >= 0 else i for i, a in enumerate(self.__data)]

N, K, L = [int(i) for i in input().split()]

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

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

for i in range(N):
    uf1.find(i)
    uf2.find(i)

from collections import Counter
Z = [(a, b) for a, b in zip(uf1.get_data(), uf2.get_data())]
C = Counter(Z)
print(*[C[z] for z in Z])

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.__data = [-1 for _ in range(size)]
    def find(self, x):
        if self.__data[x] < 0:
            return x
        else:
            self.__data[x] = self.find(self.__data[x])
            return self.__data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.__data[y] < self.__data[x]:
                x, y = y, x
            self.__data[x] += self.__data[y]
            self.__data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.__data[self.find(x)]

N, K, L = [int(i) for i in input().split()]

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

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

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.data = [-1 for _ in range(size)]
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]

N, K, L = [int(i) for i in input().split()]

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

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

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.data = [i for i in range(size)]
    def find(self, x):
        if self.data[x] != x:
            self.data[x] = self.find(self.data[x])
        return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            self.data[x] = min(x, y)
            self.data[y] = self.data[x]

N, K, L = [int(i) for i in input().split()]

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

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

from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    d[(uf1.find(i), uf2.find(i))] += 1

l = ""
for i in range(N):
    l += str(d[(uf1.find(i), uf2.find(i))]) + " "
print(l[:-1])

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, elems):
        self.parent = dict()
        for e in elems:
            self.parent[e] = e

    def root(self, e):
        if self.parent[e] == e:
            return e

        self.parent[e] = self.root(self.parent[e])
        return self.parent[e]

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

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

        rx = self.root(x)
        ry = self.root(y)
        self.parent[rx] = ry


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

for i in range(k):
    a, b = map(lambda x: int(x) - 1, input().split())
    uf1.unite(a, b)

for i in range(l):
    a, b = map(lambda x: int(x) - 1, input().split())
    uf2.unite(a, b)


ps = [(uf1.root(i), uf2.root(i)) for i in range(n)]
counts = dict()
for p in ps:
    if p in counts:
        counts[p] += 1
    else:
        counts[p] = 1


nums = [counts[p] for p in ps]
print(' '.join(map(str, nums)))

Submission status: Accepted

Solution code:
from collections import defaultdict

N, K, L = [int(a) for a in input().split(" ")]
P, Q = zip(*[[int(v) for v in input().split(" ")] for i in range(K)])
R, S = zip(*[[int(v) for v in input().split(" ")] for i in range(L)])

def find(tab, a):
    if tab[a] == -1: return a
    tab[a] = find(tab, tab[a])
    return tab[a]

def union(tab, a, b):
    pa, pb = (find(tab, a), find(tab, b))
    if pa!=pb:
        tab[pb] = pa

loads = [-1]*N
rails = [-1]*N
both = [-1]*N
for p, q in zip(P, Q):
    union(loads, p-1, q-1)

for r, s in zip(R, S):
    union(rails, r-1, s-1)

dic = defaultdict(lambda: 0)
ans = []
for i in range(N):
    key = (find(loads, i), find(rails, i))
    ans.append(key)
    dic[key] += 1

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

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
	N, K, L = map(int, input().split())
	road = [0]*K
	rail = [0]*L
	road_graph = [[i, 0] for i in range(N+1)]
	rail_graph = [[i, 0] for i in range(N+1)]

	def root(graph, i):
		parent = graph[i][0]
		if parent == i:
			return i
		return root(graph, parent)

	def is_same_tree(graph, i, j):
		return root(graph, i) == root(graph, j)

	def unite(graph, i, j):
		if is_same_tree(graph, i, j):
			return
		l = graph[root(graph, i)]
		r = graph[root(graph, j)]
		if l[1] < r[1]:
			l[0] = r[0]
			r[1] += 1
		else:
			r[0] = l[0]
			l[1] += 1

	ans_list = [""]*N

	for i in range(K):
		road[i] = list(map(int, input().split()))
		unite(road_graph, road[i][0], road[i][1])
	for i in range(L):
		rail[i] = list(map(int, input().split()))
		unite(rail_graph, rail[i][0], rail[i][1])

	ans_memo = defaultdict(int)
	road_memo = [0]*(N+1)
	rail_memo = [0]*(N+1)
	for i in range(1, N+1):
		road_root = root(road_graph, i)
		rail_root = root(rail_graph, i)
		road_memo[i] = road_root
		rail_memo[i] = rail_root
		ans_memo[(road_root, rail_root)] += 1

	for i in range(1, N+1):
		road_root = road_memo[i]
		rail_root = rail_memo[i]
		this_ans = str(ans_memo[road_root, rail_root])
		ans_list[i-1] = this_ans

	ans = " ".join(ans_list)
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n, k, l = [int(item) for item in input().split()]
pq = [[int(item) for item in input().split()] for _ in range(k)]
rs = [[int(item) for item in input().split()] for _ in range(l)]

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

UFA = UnionFind(n)
UFB = UnionFind(n)
for p, q in pq:
    UFA.union(p-1, q-1)
for r, s in rs:
    UFB.union(r-1, s-1)

par = []
for i in range(n):
    par.append([UFA.find(i), UFB.find(i), i])
par = sorted(par, key=lambda x:(x[0], x[1]))
prev_a, prev_b = -1, -1
ans = [0] * n
count = 0
member = []
for a, b, index in par:
    if prev_a != a or prev_b != b:
        for mem in member:
            ans[mem] = count
        count = 1
        member = [index]
        prev_a = a
        prev_b = b
    else:
        member.append(index)
        count += 1
for mem in member:
    ans[mem] = count
print(" ".join([str(item) for item in ans]))

Submission status: Accepted

Solution code:
from collections import defaultdict

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
        
N, K, L = map(int, input().split())

uf = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    uf.unite(p - 1, q - 1)
    
uf2 = UnionFind(N)
for i in range(L):
    r, s = map(int, input().split())
    uf2.unite(r - 1, s - 1)

d = defaultdict(int)
for i in range(N):
    n = uf.root(i)
    m = uf2.root(i)
    d[(n, m)] += 1

ans = []
for i in range(N):
    n = uf.root(i)
    m = uf2.root(i)
    ans.append(d[(n, m)])

print(* ans)