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 bisect
class UnionFind:

    # n要素で初期化
    def __init__(self,n):
        self.par = list(range(n))
        self.rank = [0]*n
        self.memo = {}

    # 木の根を求める
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    # xとyの属する集合を併合
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return None
        
        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

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

if __name__ == '__main__':
    n,k,l = map(int,input().split())
    UF_k = UnionFind(n)
    UF_l = UnionFind(n)
    for i in range(k):
        p,q = map(int,input().split())
        UF_k.unite(p-1,q-1)
    for i in range(l):
        r,s = map(int,input().split())
        UF_l.unite(r-1,s-1)
    l = []
    dic = {}
    for i in range(n):
        tmp = (UF_k.find(i),UF_l.find(i))
        l.append(tmp)
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1
    
    for fac in l:
        print(dic[fac],end=' ')

Submission status: Accepted

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

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

    def find(self, x):
        r = x
        while self.parent[r] != r:
            r = self.parent[r]
        while self.parent[x] != r:
            x, self.parent[x] = self.parent[x], r
        return r

    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.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[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.find(x) == self.find(y)

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

N, K, L = map(int, input().split())
uf1 = UnionFind(N+1)
for _ in range(K):
    p, q = map(int, input().split())
    uf1.unite(p, q)
uf2 = UnionFind(N+1)
for _ in range(L):
    r, s = map(int, input().split())
    uf2.unite(r, s)
cnt = defaultdict(int)
for i in range(1, N+1):
    cnt[(uf1.find(i), uf2.find(i))] += 1
ans = [cnt[(uf1.find(i), uf2.find(i))] for i in range(1, N+1)]
print(*ans)

Submission status: Accepted

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

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

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    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.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[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.find(x) == self.find(y)

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

N, K, L = map(int, input().split())
uf1 = UnionFind(N+1)
for _ in range(K):
    p, q = map(int, input().split())
    uf1.unite(p, q)
uf2 = UnionFind(N+1)
for _ in range(L):
    r, s = map(int, input().split())
    uf2.unite(r, s)
cnt = defaultdict(int)
for i in range(1, N+1):
    cnt[(uf1.find(i), uf2.find(i))] += 1
ans = [cnt[(uf1.find(i), uf2.find(i))] for i in range(1, N+1)]
print(*ans)

Submission status: Accepted

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

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

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    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.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[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.find(x) == self.find(y)

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

N, K, L = map(int, input().split())
uf1 = UnionFind(N+1)
for _ in range(K):
    p, q = map(int, input().split())
    uf1.unite(p, q)
uf2 = UnionFind(N+1)
cnt = [defaultdict(int) for _ in range(N+1)]
for i in range(1, N+1):
    cnt[i][uf1.find(i)] = 1
for _ in range(L):
    r, s = map(int, input().split())
    if uf2.same(r, s):
        continue
    a = uf2.find(r)
    b = uf2.find(s)
    uf2.unite(r, s)
    c = uf2.find(r)
    if a == c:
        for k, v in cnt[b].items():
            cnt[c][k] += v
    else:
        for k, v in cnt[a].items():
            cnt[c][k] += v
ans = [0] * (N+1)
for i in range(1, N+1):
    ans[i] = cnt[uf2.find(i)][uf1.find(i)]
print(*ans[1:])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
class UnionFind():
    def __init__(self, n, m = None, read = 0):
        self.n = n
        self.parents = [-1] * n
        if read:
            if m is None:
                raise ValueError("What is M")
            for i in range(m):
                a, b = map(int, input().split())
                self.union(a - 1, b - 1)

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

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

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

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

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

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

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

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

C = []
n, k, l = map(int, input().split())
UF_R = UnionFind(n, k, 1)
UF_T = UnionFind(n, l, 1)
for i in range(n):
    R = UF_R.find(i)
    T = UF_T.find(i)
    C += (R, T),
from collections import*
c = Counter(C)
print(*[c[g] for g in C])

Submission status: Accepted

Solution code:
N, M, L = [int(s) for s in input().split()]
parent_road = list(range(N))
parent_train = list(range(N))
rank_road = [0] * N
rank_train = [0] * N


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * N

    def find(self, x):
        if x == self.parent[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


edge_road = [[int(s) - 1 for s in input().split()] for _ in range(M)]
edge_train = [[int(s) - 1 for s in input().split()] for _ in range(L)]

group_road = UnionFind(N)
group_train = UnionFind(N)

for x, y in edge_road:
    group_road.union(x, y)

for x, y in edge_train:
    group_train.union(x, y)

group_count = {}
group_list = []
for i in range(N):
    gr = group_road.find(i)
    gt = group_train.find(i)
    group_list.append((gr, gt))
    if (gr, gt) in group_count.keys():
        group_count[(gr, gt)] += 1
    else:
        group_count[(gr, gt)] = 1

print(' '.join([str(group_count[g]) for g in group_list]))

Submission status: Accepted

Solution code:
from collections import deque, Counter

N, K, L = [int(s) for s in input().split()]
edge_road = [[int(s) - 1 for s in input().split()] for _ in range(K)]
edge_train = [[int(s) - 1 for s in input().split()] for _ in range(L)]
graph_road = [[] for _ in range(N)]
graph_train = [[] for _ in range(N)]

for i, j in edge_road:
    graph_road[i].append(j)
    graph_road[j].append(i)

for i, j in edge_train:
    graph_train[i].append(j)
    graph_train[j].append(i)

group_road = [0] * N
group_num = 0

visited = [False]*N

for i in range(N):
    if visited[i]:
        continue
    dq = deque([i])
    group_road[i] = group_num
    visited[i] = True
    while(dq):
        search_obj = dq.pop()
        for candidate_obj in graph_road[search_obj]:
            if not visited[candidate_obj]:
                group_road[candidate_obj] = group_num
                dq.appendleft(candidate_obj)
                visited[candidate_obj] = True
    group_num += 1


group_train = [0] * N
group_num = 0

visited = [False]*N

for i in range(N):
    if visited[i]:
        continue
    dq = deque([i])
    group_train[i] = group_num
    visited[i] = True
    while(dq):
        search_obj = dq.pop()
        for candidate_obj in graph_train[search_obj]:
            if not visited[candidate_obj]:
                group_train[candidate_obj] = group_num
                dq.appendleft(candidate_obj)
                visited[candidate_obj] = True
    group_num += 1

group_count = Counter(zip(group_road, group_train))

for gr, gt in zip(group_road, group_train):
    print(group_count[(gr, gt)], end=' ')

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 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 sama_check(self, x, y):
        return self.find(x) == self.find(y)


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

un_load = UnionFind(n)
un_train = UnionFind(n)

for i in range(k):
    p, q = map(lambda x: int(x) - 1, input().split())
    
    if not un_load.sama_check(p, q):
        un_load.union(p, q)

for i in range(l):
    r, s = map(lambda x: int(x) - 1, input().split())
    
    if not un_train.sama_check(r, s):
        un_train.union(r, s)

load_train = {}
for i in range(n):
    comb = (un_load.find(i), un_train.find(i))
    
    if comb in load_train:
        load_train[comb] += 1
    else:
        load_train[comb] = 1

for i in range(n):
    print(load_train[(un_load.par[i], un_train.par[i])])

Submission status: Accepted

Solution code:
class UF():
  def __init__(self, N):
    self.par = [-1] * N

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

  def union(self, x,y):
    p1,p2 = self.find(x), self.find(y)
    if p1 == p2: return
    if p1 > p2:
      p1,p2 = p2,p1
    self.par[p1] += self.par[p2]
    self.par[p2] = p1

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

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

for _ in range(K):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  uf_road.union(u,v)

for _ in range(L):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  uf_railway.union(u,v)

dic = {}
counter = []
for i in range(N):
  p1 = uf_road.find(i)
  p2 = uf_railway.find(i)
  counter.append((p1,p2))
  if (p1,p2) not in dic:
    dic[(p1,p2)] = 1
  else:
    dic[(p1,p2)] += 1

for i in range(N):
  print(dic[counter[i]], end=" ")

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    q = deque()
    color1 = [-1] * (n + 1)
    color2 = [-1] * (n + 1)
    for i in range(1, n + 1):
        if color1[i] == -1:
            color1[i] = i
            q.append(i)
            while q:
                p = q.popleft()
                for j in G[p]:
                    if color1[j] == -1:
                        color1[j] = color1[p]
                        q.append(j)
        if color2[i] == -1:
            color2[i] = i
            q.append(i)
            while q:
                p = q.popleft()
                for j in H[p]:
                    if color2[j] == -1:
                        color2[j] = color2[p]
                        q.append(j)
    group = [color1[i] + 200000 * color2[i] for i in range(n + 1)]
    return group

n, k, l = map(int, input().split())
G = [[] for _ in range(n + 1)]
H = [[] for _ in range(n + 1)]
for _ in range(k):
    p, q = map(int, input().split())
    G[p].append(q)
    G[q].append(p)
for _ in range(l):
    r, s = map(int, input().split())
    H[r].append(s)
    H[s].append(r)
group = bfs()
d = {}
for i in range(1, n + 1):
    if group[i] in d:
        d[group[i]] += 1
    else:
        d[group[i]] = 1
ans = [0] * n
for i in range(1, n + 1):
    ans[i - 1] = d[group[i]]
print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

    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 find(self, x):          #親を出力
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

    def size(self, x):          #グループの要素数
        return -self.parents[self.find(x)]

    def members(self, x):       #xと同じグループの要素
        root = self.find(x)
        return {i for i in range(self.n) if self.find(i) == root}

    def roots(self):            #親の要素一覧
        return {i for i, x in enumerate(self.parents) if x < 0}

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

    def all_group_members(self):      #グループのメンバー一覧
        return {r: self.members(r) for r in self.roots()}

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

################

from collections import Counter

def main():
    N, K, L = map(int, input().split())
    ufK = UnionFind(N)
    ufL = UnionFind(N)
    for i in range(K):
        a,b = map(int,input().split())
        ufK.union(a-1, b-1)
    for i in range(L):
        a,b = map(int,input().split())
        ufL.union(a-1, b-1)

    ps=[(ufK.find(i),ufL.find(i)) for i in range(N)]
    cps = Counter(ps)
    ret = [0]*N
    for i in range(N):
        ret[i] =cps[ps[i]]
    print(*ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

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

import sys
input = sys.stdin.buffer.readline
from collections import Counter
n,k,l=map(int,input().split())
uf1=UnionFind(n)
uf2=UnionFind(n)
for _ in range(k):
	uf1.unite(*map(int,input().split()))
for _ in range(l):
	uf2.unite(*map(int,input().split()))
ps=[(uf1.find(i),uf2.find(i)) for i in range(1,n+1)]
C=Counter(ps)
ans=[]
for i in range(n):
	if ps[i][0]<0 or ps[i][1]<0:
		ans.append(0)
	else:
		ans.append(C[ps[i]])
print(*ans)

Submission status: Accepted

Solution code:
from collections import Counter
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

N,K,L = map(int,input().split())
l = []
ufp = UnionFind(N)
ufr = UnionFind(N)
for i in range(K):
    p,q = map(int, input().split())
    ufp.union(p-1, q-1)
for i in range(L):
    r,s = map(int,input().split())
    ufr.union(r-1, s-1)

for i in range(N):
    tup = (ufp.find(i), ufr.find(i))
    l.append(tup)
c = Counter(l)
for i in range(N):
    # 個数を調べたいデータを入れると、その個数が返される
    print(c[l[i]], end=" ")

Submission status: Accepted

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

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            # 経路圧縮
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

N,K,L = map(int,input().split())
l = []
ufp = UnionFind(N)
ufr = UnionFind(N)
for i in range(K):
    p,q = map(int, input().split())
    ufp.union(p-1, q-1)
for i in range(L):
    r,s = map(int,input().split())
    ufr.union(r-1, s-1)

for i in range(N):
    tup = (ufp.find(i), ufr.find(i))
    l.append(tup)
c = Counter(l)
for i in range(N):
    # 個数を調べたいデータを入れると、その個数が返される
    print(c[l[i]], end=" ")

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
class UF():
  def __init__(self, N):
    self.parents = [-1] * (N+1)

  def union(self, f, t):
    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return

    if self.parents[p1] > self.parents[p2]:
      p1,p2 = p2,p1
    self.parents[p1] += self.parents[p2]
    self.parents[p2] = p1

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

  # def members(self, n):
  #   root = self.find(n)
  #   if root == -1:
  #     return []
  #   import pdb; pdb.set_trace()
  #   return [ i for i, p in enumerate(self.parents) if self.find(i) == root]

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

for _ in range(K):
  f,t = map(int, input().split())
  uf_road.union(f,t)

for _ in range(L):
  f,t = map(int, input().split())
  uf_railway.union(f,t)

l = []
for i in range(1, N+1):
  l.append((uf_road.find(i), uf_railway.find(i)))

c = Counter(l)
for i in range(N):
  print(c[l[i]], end=" ")

Submission status: Accepted

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

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

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

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

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

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


gp = Unionfind(n)
gr = Unionfind(n)

for i in range(k):
    a,b = map(int,input().split())
    gp.union(a-1,b-1)
for i in range(l):
    a,b = map(int,input().split())
    gr.union(a-1,b-1)

l = []
dic = {}
for i in range(n):
    a = gp.find(i) 
    b = gr.find(i)
    s = (a,b)
    l.append(s)
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1
ans = []
for i in range(n):
    ans.append(dic[l[i]])
print(*ans)

Submission status: Accepted

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

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

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

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

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

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


gp = Unionfind(n)
gr = Unionfind(n)

for i in range(k):
    a,b = map(int,input().split())
    gp.union(a-1,b-1)
for i in range(l):
    a,b = map(int,input().split())
    gr.union(a-1,b-1)

l = []
dic = {}
for i in range(n):
    a = gp.find(i) 
    b = gr.find(i)
    if a < 0:
        a = i
    if b < 0:
        b = i
    s = (a,b)
    l.append(s)
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1
ans = []
for i in range(n):
    ans.append(dic[l[i]])
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

n,k,l = map(int,input().split())
ep = [[] for i in range(n)]
er = [[] for i in range(n)]

gp = [-1]*n
gr = [-1]*n

for i in range(k):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ep[a].append(b)
    ep[b].append(a)
for i in range(l):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    er[a].append(b)
    er[b].append(a)

def dfs(e,g):
    count = 0
    for i in range(n):
        if g[i] == -1:
            g[i] = count

            q = deque([])
            q.append(i)
            while q:
                now = q.pop()

                for nex in e[now]:
                    if g[nex] == -1:
                        g[nex] = g[now]
                        q.append(nex)
            count += 1

    return g
gp = dfs(ep,gp)
gr = dfs(er,gr)
l = []
dic = {}
for i in range(n):
    s = (gp[i],gr[i])
    l.append(s)
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1
ans = []
for i in range(n):
    ans.append(dic[l[i]])
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

n,k,l = map(int,input().split())
ep = [[] for i in range(n)]
er = [[] for i in range(n)]

gp = [-1]*n
gr = [-1]*n

for i in range(k):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ep[a].append(b)
    ep[b].append(a)
for i in range(l):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    er[a].append(b)
    er[b].append(a)

def dfs(e,g):
    count = 0
    for i in range(n):
        if g[i] == -1:
            g[i] = count

            q = deque([])
            q.append(i)
            while q:
                now = q.pop()

                for nex in e[now]:
                    if g[nex] == -1:
                        g[nex] = g[now]
                        q.append(nex)
            count += 1

    return g
gp = dfs(ep,gp)
gr = dfs(er,gr)
l = []
dic = {}
for i in range(n):
    s = (gp[i],gr[i])
    l.append(s)
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1
ans = [0]*n

for i in range(n):
    ans[i] = dic[l[i]]
print(*ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class UnionFind(object):
    def __init__(self, n = 1):
        self.link = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.link[x] == x:
            return x

        # re-connect union find to make the height of tree lower
        # you can use while, but recursion makes it easier to reconnect
        self.link[x] = self.find(self.link[x])
        return self.link[x]

    def is_same(self, x, y):
        return self.link[x] == self.link[y]

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

        if self.size[x] < self.size[y]:
            x, y = y, x
        self.link[y] = x
        self.size[x] += self.size[y]
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]

# from union_find import *

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

u1 = UnionFind(n)
u2 = UnionFind(n)


for i in range(k):
    p, q = map(lambda x: int(x) - 1, readline().split())
    u1.unite(p, q)

for i in range(l):
    r, s = map(lambda x: int(x) - 1, readline().split())
    u2.unite(r, s)

c = defaultdict(int)

for i in range(n):
    c[(u1.find(i), u2.find(i))] += 1

for i in range(n):
    print(c[u1.find(i), u2.find(i)])

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline
N,K,L=map(int,input().split())

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]
def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x
def is_same(x,y):
  return get_par(x) == get_par(y)

par_list=list(range(N+1))
for _ in range(K):
  p,q=map(int,input().split())
  merge(p,q)
for i in range(1,N+1):
  par_list[i]=get_par(i)
par_list_road=par_list[:]
  
par_list=list(range(N+1))
for _ in range(L):
  r,s=map(int,input().split())
  merge(r,s)
for i in range(1,N+1):
  par_list[i]=get_par(i)
par_list_rail=par_list[:]

#print(par_list_road)
#print(par_list_rail)
answer_dic=defaultdict(int)
for i in range(1,N+1):
  road_i=par_list_road[i]
  rail_i=par_list_rail[i]
  answer_dic[(road_i,rail_i)]+=1
  
answer_list=[]
for i in range(1,N+1):
  road_i=par_list_road[i]
  rail_i=par_list_rail[i]
  answer_list.append(answer_dic[(road_i,rail_i)])
  
print(*answer_list)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K,L=map(int,input().split())
    class UnionFind:
        def __init__(self,n):
            self.par=[i for i in range(n)]
            self.siz=[1]*n
            
        def root(self,x):
            while self.par[x]!=x:
                self.par[x]=self.par[self.par[x]]
                x=self.par[x]
            return x
        
        def unite(self,x,y):
            x=self.root(x)
            y=self.root(y)
            if x==y:
                return False
            if self.siz[x]<self.siz[y]:
                x,y=y,x
            self.siz[x]+=self.siz[y]
            self.par[y]=x
            return True
        
        def is_same(self,x,y):
            return self.root(x)==self.root(y)
        
        def size(self,x):
            return self.siz[self.root(x)]
    d=UnionFind(N)
    t=UnionFind(N)
    for _ in range(K):
        p,q=map(int1,input().split())
        d.unite(p,q)
    for _ in range(L):
        r,s=map(int1,input().split())
        t.unite(r,s)
    l=[]
    for i in range(N):
        l.append((d.root(i),t.root(i)))
    c=Counter(l)
    for i in range(N):
        print(c[l[i]],end=' ')

if __name__ == '__main__':
    main()