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: Time Limit Exceeded

Solution code:
class UnionFind:

    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.size = size
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        # 集合の代表を求める
        children = []
        while self.table[x] >= 0:
            children.append(x)
            x = self.table[x]
        for c in children:
            self.table[c] = x
        return x

    def union(self, x, y):
        # 併合
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] >= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
        return self.table[s1]

n,k,l= map(int, input().split())
road = UnionFind(n+1)
train = UnionFind(n+1)

for i in range(k):
    p,q = map(int, input().split())
    road.union(p, q)
for i in range(l):
    p,q = map(int, input().split())
    train.union(p,q)
con = [1 for i in range(n)]
for i in range(1,n):
    for j in range(i+1, n+1):
        if road.find(i) == road.find(j) and train.find(i) == train.find(j):
            con[i-1] += 1
            con[j-1] += 1
print(*con, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
class UnionFind3:
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                # 小さいほうが個数が多い
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False


n, k, l = map(int, input().split())
ufd, ufr = UnionFind3(n), UnionFind3(n)
for _ in range(k):
    p, q = map(int, input().split())
    ufd.union(p - 1, q - 1)
for _ in range(l):
    r, s = map(int, input().split())
    ufr.union(r - 1, s - 1)
result = [1] * n
for i in range(n):
    for j in range(i + 1, n):
        if ufd.find(i) == ufd.find(j) and ufr.find(i) == ufr.find(j):
            result[i] += 1
            result[j] += 1
print(*result)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3


class UnionFind(object):

    def __init__(self, number_of_nodes):
        self.par = list(range(number_of_nodes))
        self.rank = [0] * number_of_nodes

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

    def in_the_same_set(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    n, k, l = (int(x) for x in input().split())
    uf_roads = UnionFind(n)
    for _ in range(k):
        p, q = (int(x) - 1 for x in input().split())
        uf_roads.unite(p, q)
    uf_rails = UnionFind(n)
    for _ in range(l):
        r, s = (int(x) - 1 for x in input().split())
        uf_rails.unite(r, s)
    ans = [sum(1 for y in range(n) if
               uf_roads.in_the_same_set(x, y) and
               uf_rails.in_the_same_set(x, y)) for x in range(n)]
    print(" ".join(str(z) for z in ans))


if __name__ == '__main__':
    main()

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import gc
import sys
sys.setrecursionlimit(10**7)
from collections import Counter
from collections import defaultdict

n,k,l=map(int,input().split())
p=[0]*(k+1)
q=[0]*(k+1)
rd=[[] for _ in range(n+1)]

for i in range(k):
    a,b=map(int,input().split())
    p[i],q[i]=a,b
    rd[a].append(b)
    rd[b].append(a)
    
    
p=[0]*(l+1)
q=[0]*(l+1)
rw=[[] for _ in range(n+1)]
for i in range(l):
    a,b=map(int,input().split())
    p[i],q[i]=a,b
    rw[a].append(b)
    rw[b].append(a)
del p,q
gc.collect()
prd=[i for i in range(n+1)]


def union(x,y):
    rx=root(x)
    ry=root(y)
    if rx==ry:
        return
    p[rx]=ry
    
def root(x):
    if p[x]==x:
        return x
    p[x]=root(p[x])
    return p[x]
    

#print(rd)
#print(rw)

p=prd
for i in range(1,n+1):
    for j in rd[i]:
        union(i,j)
for i in range(1,n+1):
    rt=root(i)
    prd[i]=rt
#    cnt[i].append(rt)

p=[i for i in range(n+1)]
for i in range(1,n+1):
    for j in rw[i]:
        union(i,j)
for i in range(1,n+1):
    rt=root(i)
    p[i]=rt
#    cnt[i].append(rt)
#print(cnt)
#c=Counter(cnt)
dc=defaultdict(int)
for i in range(1,n+1):
    dc[prd[i],p[i]] += 1

#for i in range(n+1):
print(*[dc[prd[i],p[i]] for i in range(1,n+1)])

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import gc
import sys
sys.setrecursionlimit(10**7)
from collections import Counter
from collections import defaultdict

n,k,l=map(int,input().split())
p=[0]*(k+1)
q=[0]*(k+1)
rd=[[] for _ in range(n+1)]
r=[0]*(l+1)
s=[0]*(l+1)
rw=[[] for _ in range(n+1)]

for i in range(k):
    a,b=map(int,input().split())
    p[i],q[i]=a,b
    rd[a].append(b)
    rd[b].append(a)
for i in range(l):
    a,b=map(int,input().split())
    r[i],s[i]=a,b
    rw[a].append(b)
    rw[b].append(a)
del p,q,r,s
gc.collect()
prd=[i for i in range(n+1)]


def union(x,y):
    rx=root(x)
    ry=root(y)
    if rx==ry:
        return
    p[rx]=ry
    
def root(x):
    if p[x]==x:
        return x
    p[x]=root(p[x])
    return p[x]
    

#print(rd)
#print(rw)

p=prd
for i in range(1,n+1):
    for j in rd[i]:
        union(i,j)
for i in range(1,n+1):
    rt=root(i)
    prd[i]=rt
#    cnt[i].append(rt)

p=[i for i in range(n+1)]
for i in range(1,n+1):
    for j in rw[i]:
        union(i,j)
for i in range(1,n+1):
    rt=root(i)
    p[i]=rt
#    cnt[i].append(rt)
#print(cnt)
#c=Counter(cnt)
dc=defaultdict(int)
for i in range(1,n+1):
    dc[prd[i],p[i]] += 1

#for i in range(n+1):
print(*[dc[prd[i],p[i]] for i in range(1,n+1)])

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)
from collections import Counter
from collections import defaultdict

n,k,l=map(int,input().split())
p=[0]*(k+1)
q=[0]*(k+1)
rd=[[] for _ in range(n+1)]
r=[0]*(l+1)
s=[0]*(l+1)
rw=[[] for _ in range(n+1)]

for i in range(k):
    a,b=map(int,input().split())
    p[i],q[i]=a,b
    rd[a].append(b)
    rd[b].append(a)
for i in range(l):
    a,b=map(int,input().split())
    r[i],s[i]=a,b
    rw[a].append(b)
    rw[b].append(a)

prd=[i for i in range(n+1)]


def union(x,y):
    rx=root(x)
    ry=root(y)
    if rx==ry:
        return
    p[rx]=ry
    
def root(x):
    if p[x]==x:
        return x
    p[x]=root(p[x])
    return p[x]
    

#print(rd)
#print(rw)

p=prd
for i in range(1,n+1):
    for j in rd[i]:
        union(i,j)
for i in range(1,n+1):
    rt=root(i)
    prd[i]=rt
#    cnt[i].append(rt)

p=[i for i in range(n+1)]
for i in range(1,n+1):
    for j in rw[i]:
        union(i,j)
for i in range(1,n+1):
    rt=root(i)
    p[i]=rt
#    cnt[i].append(rt)
#print(cnt)
#c=Counter(cnt)
dc=defaultdict(int)
for i in range(1,n+1):
    dc[prd[i],p[i]] += 1

#for i in range(n+1):
print(*[dc[prd[i],p[i]] for i in range(1,n+1)])

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)
from collections import Counter
from collections import defaultdict

n,k,l=map(int,input().split())
p=[0]*(k+1)
q=[0]*(k+1)
rd=[[] for _ in range(n+1)]
r=[0]*(l+1)
s=[0]*(l+1)
rw=[[] for _ in range(n+1)]

for i in range(k):
    a,b=map(int,input().split())
    p[i],q[i]=a,b
    rd[a].append(b)
    rd[b].append(a)
for i in range(l):
    a,b=map(int,input().split())
    r[i],s[i]=a,b
    rw[a].append(b)
    rw[b].append(a)

prd=[i for i in range(n+1)]


def union(x,y):
    rx=root(x)
    ry=root(y)
    if rx==ry:
        return
    p[rx]=ry
    
def root(x):
    if p[x]==x:
        return x
    p[x]=root(p[x])
    return p[x]
    
cnt=[[] for _ in range(n+1)]
#print(rd)
#print(rw)

p=prd
for i in range(1,n+1):
    for j in rd[i]:
        union(i,j)
for i in range(1,n+1):
    rt=root(i)
    prd[i]=rt
#    cnt[i].append(rt)

p=[i for i in range(n+1)]
for i in range(1,n+1):
    for j in rw[i]:
        union(i,j)
for i in range(1,n+1):
    rt=root(i)
    p[i]=rt
#    cnt[i].append(rt)
#print(cnt)
#c=Counter(cnt)
dc=defaultdict(int)
for i in range(1,n+1):
    dc[prd[i],p[i]] += 1

#for i in range(n+1):
print(*[dc[prd[i],p[i]] for i in range(1,n+1)])

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from collections import defaultdict

n,k,l=map(int,input().split())
p=[0]*(k+1)
q=[0]*(k+1)
rd=[[] for _ in range(n+1)]
r=[0]*(l+1)
s=[0]*(l+1)
rw=[[] for _ in range(n+1)]

for i in range(k):
    a,b=map(int,input().split())
    p[i],q[i]=a,b
    rd[a].append(b)
    rd[b].append(a)
for i in range(l):
    a,b=map(int,input().split())
    r[i],s[i]=a,b
    rw[a].append(b)
    rw[b].append(a)

prd=[i for i in range(n+1)]


def union(x,y):
    rx=root(x)
    ry=root(y)
    if rx==ry:
        return
    p[rx]=ry
    
def root(x):
    if p[x]==x:
        return x
    p[x]=root(p[x])
    return p[x]
    
cnt=[[] for _ in range(n+1)]
#print(rd)
#print(rw)

p=prd
for i in range(1,n+1):
    for j in rd[i]:
        union(i,j)
for i in range(1,n+1):
    rt=root(i)
    prd[i]=rt
#    cnt[i].append(rt)

p=[i for i in range(n+1)]
for i in range(1,n+1):
    for j in rw[i]:
        union(i,j)
for i in range(1,n+1):
    rt=root(i)
    p[i]=rt
#    cnt[i].append(rt)
#print(cnt)
#c=Counter(cnt)
dc=defaultdict(int)
for i in range(1,n+1):
    dc[prd[i],p[i]] += 1

#for i in range(n+1):
print(*[dc[prd[i],p[i]] for i in range(1,n+1)])

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from collections import defaultdict

n,k,l=map(int,input().split())
p=[0]*(k+1)
q=[0]*(k+1)
rd=[[] for _ in range(n+1)]
r=[0]*(l+1)
s=[0]*(l+1)
rw=[[] for _ in range(n+1)]

for i in range(k):
    a,b=map(int,input().split())
    p[i],q[i]=a,b
    rd[a].append(b)
    rd[b].append(a)
for i in range(l):
    a,b=map(int,input().split())
    r[i],s[i]=a,b
    rw[a].append(b)
    rw[b].append(a)

prd=[i for i in range(n+1)]
prw=[i for i in range(n+1)]

def union(x,y):
    rx=root(x)
    ry=root(y)
    if rx==ry:
        return
    p[rx]=ry
    
def root(x):
    if p[x]==x:
        return x
    p[x]=root(p[x])
    return p[x]
    
cnt=[[] for _ in range(n+1)]
#print(rd)
#print(rw)

p=prd
for i in range(1,n+1):
    for j in rd[i]:
        union(i,j)
for i in range(1,n+1):
    rt=root(i)
    prd[i]=rt
#    cnt[i].append(rt)

p=prw
for i in range(1,n+1):
    for j in rw[i]:
        union(i,j)
for i in range(1,n+1):
    rt=root(i)
    prw[i]=rt
#    cnt[i].append(rt)
#print(cnt)
#c=Counter(cnt)
dc=defaultdict(int)
for i in range(1,n+1):
    dc[prd[i],prw[i]] += 1

#for i in range(n+1):
print(*[dc[prd[i],prw[i]] for i in range(1,n+1)])

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from collections import defaultdict

n,k,l=map(int,input().split())
p=[0]*(k+1)
q=[0]*(k+1)
rd=[[] for _ in range(n+1)]
r=[0]*(l+1)
s=[0]*(l+1)
rw=[[] for _ in range(n+1)]

for i in range(k):
    a,b=map(int,input().split())
    p[i],q[i]=a,b
    rd[a].append(b)
    rd[b].append(a)
for i in range(l):
    a,b=map(int,input().split())
    r[i],s[i]=a,b
    rw[a].append(b)
    rw[b].append(a)

prd=[i for i in range(n+1)]
prw=[i for i in range(n+1)]

def union(x,y):
    rx=root(x)
    ry=root(y)
    if rx==ry:
        return
    p[rx]=ry
    
def root(x):
    if p[x]==x:
        return x
    p[x]=root(p[x])
    return p[x]
    
cnt=[[] for _ in range(n+1)]
#print(rd)
#print(rw)

p=prd
for i in range(1,n+1):
    for j in rd[i]:
        union(i,j)
for i in range(1,n+1):
    rt=root(i)
    prd[i]=rt
    cnt[i].append(rt)

p=prw
for i in range(1,n+1):
    for j in rw[i]:
        union(i,j)
for i in range(1,n+1):
    rt=root(i)
    prw[i]=rt
    cnt[i].append(rt)
#print(cnt)
#c=Counter(cnt)
dc=defaultdict(int)
for i in cnt:
    dc[','.join([str(c) for c in i])] += 1

#for i in range(n+1):
print(*[dc[','.join([str(c) for c in cnt[i]])] for i in range(1,n+1)])

Submission status: Accepted

Solution code:
from collections import Counter
import sys


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    n, k, l = map(int, sys.stdin.buffer.readline().split())
    a = UnionFind(n)
    b = UnionFind(n)
    cnt = 0
    for x in sys.stdin.buffer.readlines():
        p, q = map(int, x.split())
        cnt += 1
        if cnt <= k:
            a.union(p-1, q-1)
        else:
            b.union(p-1, q-1)

    pairs = [(a._root(i), b._root(i)) for i in range(n)]
    d = Counter(pairs)
    ans = [d[x] for x in pairs]
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
from collections import defaultdict

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

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

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

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

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x_root == y_root):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

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

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

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

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

n,k,l = map(int,readline().split())
pqrs = list(map(int,read().split()))
pq = pqrs[:2*k]
rs = pqrs[2*k:]

uf_l = UnionFind(n+1)
uf_t = UnionFind(n+1)

for uf,link in zip([uf_l,uf_t],[pq,rs]):
    it = iter(link)
    for a,b in zip(it,it):
        uf.union(a,b)

d = defaultdict(lambda : set())
for i in range(n+1):
    root_l = uf_l.find(i)
    root_t = uf_t.find(i)
    d[root_l * 10**6 + root_t].add(i)

ans = [0] * (n+1)
for s in d.values():
    len_s = len(s)
    for i in s:
        ans[i] = len_s

print(' '.join(map(str,ans[1:])))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = float(10 ** 5)
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.size = [1] * n
        # self.group_num = n

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

    def get_size(self, x):
        r = self.root(x)
        return self.size[r]

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

    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]


n, k, l = LI()

u1 = UnionFind(n)
u2 = UnionFind(n)
for _ in range(k):
    p, q = LI()
    u1.union(p - 1, q - 1)

for _ in range(l):
    r, s = LI()
    u2.union(r - 1, s - 1)


D = defaultdict(int)
for i in range(n):
    D[(u1.root(i), u2.root(i))] += 1

for j in range(n):
    print(D[(u1.root(j), u2.root(j))], end=" ")

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) #親ノード
        self.size = [1]*n #グループの要素数
 
    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): #merge(x,y): xのいる組とyのいる組をまとめる
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x #xの要素数が大きいように
        self.size[x] += self.size[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じ組ならTrue
        return self.root(x) == self.root(y)
        
    def getsize(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

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

UF1 = UnionFind(n)
UF2 = UnionFind(n)

for _ in range(k):
    p,q = map(int,readline().split())
    UF1.merge(p-1,q-1)

for _ in range(l):
    r,s = map(int,readline().split())
    UF2.merge(r-1,s-1)

from collections import Counter
d = Counter()
for i in range(n):
    p1 = UF1.root(i)
    p2 = UF2.root(i)
    d[(p1,p2)] += 1

ans = [0]*n
for i in range(n):
    p1 = UF1.root(i)
    p2 = UF2.root(i)
    ans[i] = d[(p1,p2)]

print(*ans)

Submission status: Accepted

Solution code:
import sys

class Dsu:
	def __init__(self, n):
		self.n = n
		self.par = [i for i in range(n)]
	def root(self, x):
		path = []
		while self.par[x] != x:
			path.append(x)
			x = self.par[x]
		for i in path:
			self.par[i] = x
		return x
	def join(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x != y:
			self.par[x] = self.par[y]

input = sys.stdin.readline
n, k, l = map(int, input().split())
road = Dsu(n)
rail = Dsu(n)
for i in range(k):
	p, q = map(int, input().split())
	road.join(p - 1, q - 1)
for i in range(l):
	p, q = map(int, input().split())
	rail.join(p - 1, q - 1)
d = dict()
res = []
for i in range(n):
	d[road.root(i), rail.root(i)] = d.get((road.root(i), rail.root(i)), 0) + 1
for i in range(n):
	res.append(d[road.root(i), rail.root(i)])
print(' '.join(map(str, res)))

Submission status: Accepted

Solution code:
from collections import defaultdict


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

    # 検索
    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        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(int, input().split())
uf1 = UnionFind(n)
uf2 = UnionFind(n)
for _ in range(k):
    a, b = map(int, input().split())
    uf1.unite(a - 1, b - 1)
for _ in range(l):
    a, b = map(int, input().split())
    uf2.unite(a - 1, b - 1)
d = defaultdict(int)
for i in range(n):
    d[(uf1.find(i), uf2.find(i))] += 1
ans = [0] * n
for i in range(n):
    ans[i] = d[(uf1.find(i), uf2.find(i))]
print(*ans)

Submission status: Accepted

Solution code:
import collections
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 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]
    
N, K, L = map(int, input().split())
road = UnionFind(N)
train = UnionFind(N)
pair = []
ans = []
for i in range(K):
    p, q = map(int, input().split())
    road.union(p-1, q-1)
for i in range(L):
    r, s = map(int, input().split())
    train.union(r-1, s-1)
for i in range(N):
    pair.append((road.find(i), train.find(i)))
c = collections.Counter(pair)
for i in range(N):
    ans.append(c[(road.find(i), train.find(i))])
print(*ans)

Submission status: Accepted

Solution code:
n,k,l = map(int,input().split())
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())
uf1 = UnionFind(n+1)
uf2 = UnionFind(n+1)
for i in range(k):
    a,b = map(int,input().split())
    uf1.union(a,b)
for i in range(l):
    a,b = map(int,input().split())
    uf2.union(a,b)
root1 = [uf1.find(i) for i in range(1,n+1)]
root2 = [uf2.find(i) for i in range(1,n+1)]
check = [[root1[i],root2[i],i] for i in range(n)]
check.sort(key=lambda x: (x[0],x[1]))
ans = [0]*n
cnt = 1
wait = []
for i in range(n-1):
  if cnt == 1:
    wait.append(check[i][2])
  if check[i][:2] == check[i+1][:2]:
    cnt += 1
    wait.append(check[i+1][2])
  else:
    for j in wait:
      ans[j] = cnt
    wait = []
    cnt = 1
if cnt == 1:
  ans[check[n-1][2]] = 1
else:
  for j in wait:
    ans[j] = cnt
print(*ans)

Submission status: Accepted

Solution code:
from collections import Counter
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.par=[i for i in range(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 unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        if self.size[x]>=self.size[y]:
            self.par[y]=x
            self.size[x]+=self.size[y]
        else:
            self.par[x]=y
            self.size[y]+=self.size[x]
n,k,l=map(int,input().split())
uf1=UnionFind(n)
uf2=UnionFind(n)
for _ in range(k):
    u,v=map(int,input().split())
    uf1.unite(u-1,v-1)
for _ in range(l):
    u,v=map(int,input().split())
    uf2.unite(u-1,v-1)
cc=Counter()
for i in range(n):
    cc[(uf1.find(i),uf2.find(i))]+=1
ans=[cc[(uf1.find(i),uf2.find(i))] for i in range(n)]
print(*ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

n,k,l=map(int,input().split())
uf1=UnionFind(n)
uf2=UnionFind(n)
for _ in range(k):
  u,v=map(int,input().split())
  uf1.unite(u-1,v-1)
for _ in range(l):
  u,v=map(int,input().split())
  uf2.unite(u-1,v-1)
d=defaultdict(int)
for i in range(n):
  d[(uf1.find(i),uf2.find(i))]+=1
ans=[d[(uf1.find(i),uf2.find(i))] for i in range(n)]
print(*ans)

Submission status: Accepted

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans


N,K,L=map(int,input().split())
ufload=UnionFindVerSize(N)
for i in range(0,K):
    p,q=map(int,input().split())
    ufload.unite(p-1,q-1)
ufrail=UnionFindVerSize(N)
for i in range(0,L):
    r,s=map(int,input().split())
    ufrail.unite(r-1,s-1)

data=[]
for i in range(0,N):
    data.append([ufload.find_root(i),ufrail.find_root(i),i])

data.sort()
ans=[0 for i in range(0,N)]
start=0
end=0
count=1
for i in range(0,N-1):
    if data[i][0]==data[i+1][0] and data[i][1]==data[i+1][1]:
        count+=1
    else:
        end=start+count-1
        for j in range(start,end+1):
            ans[data[j][2]]=count
        start=end+1
        count=1

end=start+count-1
for j in range(start,end+1):
    ans[data[j][2]]=count
start=end+1
count=1

print(*ans)