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:
from sys import stdin

def find(parent, i):
  if parent[i] == i:
    return i
  parent[i] = find(parent, parent[i])
  return parent[i]

def unite(parent, i, j):
  i = find(parent, i)
  j = find(parent, j)
  if i == j:
    return
  parent[i] = j

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

roads = list(range(n))
rails = list(range(n))

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

for i in range(l):
  p, q = map(int, stdin.readline().split())
  unite(rails, p - 1, q - 1)

d = {}
for i in range(n):
  t = (find(roads, i), find(rails, i))
  if t in d:
    d[t] += 1
  else:
    d[t] = 1

print(*[d[(find(roads, i), find(rails, i))] for i in range(n)])

Submission status: Accepted

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

def Find(x, par):
  if par[x] < 0:
    return x
  else:
    # 経路圧縮
    par[x] = Find(par[x], par)
    return par[x]

def Unite(x, y, par, rank):
  x = Find(x, par)
  y = Find(y, par)
  
  if x != y:
    # rankの低い方を高い方につなげる
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
def Size(x, par):
  return -par[Find(x)]

n, k, l = map(int, input().split())
rpar = [-1]* n
tpar = [-1]* n
rrank = [0]*n
trank = [0]*n

for i in range(k):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, rpar, rrank) 

for i_ in range(l):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, tpar, trank)

d = {}
IDs = [0]*n
for j in range(n):
  ID = Find(j, rpar)+(Find(j, tpar)+1)*10**8
  IDs[j] = ID
  if ID in d:
    d[ID] += 1
  else:
    d[ID] = 1

for j_ in range(n):
  print(d[IDs[j_]])

Submission status: Accepted

Solution code:
def Find(x, par):
  if par[x] < 0:
    return x
  else:
    # 経路圧縮
    par[x] = Find(par[x], par)
    return par[x]

def Unite(x, y, par, rank):
  x = Find(x, par)
  y = Find(y, par)
  
  if x != y:
    # rankの低い方を高い方につなげる
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
def Size(x, par):
  return -par[Find(x)]

n, k, l = map(int, input().split())
rpar = [-1]* n
tpar = [-1]* n
rrank = [0]*n
trank = [0]*n

for i in range(k):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, rpar, rrank) 

for i_ in range(l):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, tpar, trank)

d = {}
IDs = [0]*n
for j in range(n):
  ID = Find(j, rpar)+(Find(j, tpar)+1)*10**8
  IDs[j] = ID
  if ID in d:
    d[ID] += 1
  else:
    d[ID] = 1

for j_ in range(n):
  print(d[IDs[j_]])

Submission status: Accepted

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

def Find(x, par):
  if par[x] < 0:
    return x
  else:
    # 経路圧縮
    par[x] = Find(par[x], par)
    return par[x]

def Unite(x, y, par, rank):
  x = Find(x, par)
  y = Find(y, par)
  
  if x != y:
    # rankの低い方を高い方につなげる
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
def Size(x, par):
  return -par[Find(x)]

n, k, l = map(int, input().split())
rpar = [-1]* n
tpar = [-1]* n
rrank = [0]*n
trank = [0]*n

for i in range(k):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, rpar, rrank) 

for i_ in range(l):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, tpar, trank)

d = {}
IDs = [0]*n
for j in range(n):
  ID = Find(j, rpar)+(Find(j, tpar)+1)*10**8
  IDs[j] = ID
  if ID in d:
    d[ID] += 1
  else:
    d[ID] = 1

ans = ''
for j_ in range(n):
  if j_ != 0:
    ans += ' '
  ans += str(d[IDs[j_]])
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7




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

table1 = [-1] * n
table2 = [-1] * n
def find(x, table):
    if table[x] < 0:
        return x
    table[x] = find(table[x], table)
    return table[x]


def union(x, y, table):
    r1 = find(x, table)
    r2 = find(y, table)
    if r1 == r2:
        return
    d1 = table[r1]
    d2 = table[r2]
    if d1 <= d2:
        table[r2] = r1
        if d1 == d2:
            table[r1] -= 1
    else:
        table[r1] = r2



for i in range(k):
    u, v = map(int, input().split())
    union(u - 1, v - 1, table1)


for i in range(l):
    u, v = map(int, input().split())
    union(u - 1, v - 1, table2)


f = defaultdict(int)
for i in range(n):
    f[(find(i, table1), find(i, table2))] += 1



print(*[f[(find(j, table1), find(j, table2))] for j in range(n)])

Submission status: Accepted

Solution code:
N, K, L = map(int, input().split())
E = [[] for i in range(N)]
for i in range(K):
  p, q = map(int, input().split())
  E[p-1].append(q-1)
  E[q-1].append(p-1)
F = [[] for i in range(N)]
for i in range(L):
  r, s = map(int, input().split())
  F[r-1].append(s-1)
  F[s-1].append(r-1)
C = list(range(N))
for n in range(N):
  if C[n] != n:
    continue
  q = [n]
  while q:
    c = q.pop()
    ds = E[c]
    for d in ds:
      if C[d] != n:
        C[d] = n
        q.append(d)
D = list(range(N))
for n in range(N):
  if D[n] != n:
    continue
  q = [n]
  while q:
    c = q.pop()
    ds = F[c]
    for d in ds:
      if D[d] != n:
        D[d] = n
        q.append(d)
#print(C)
#print(D)
Nums = {}
for i in range(N):
  c, d = C[i], D[i]
  if (c, d) in Nums:
    Nums[(c, d)] += 1
  else:
    Nums[(c, d)] = 1
rs = []
for i in range(N):
  c, d = C[i], D[i]
  r = Nums[(c, d)]
  rs.append(r)
print(" ".join(map(str, rs)))

Submission status: Accepted

Solution code:
from collections import defaultdict
def build_tree(N, edges):
    root_list = [i for i in range(N)]
    for p, q in edges:
        p -= 1
        q -= 1
        root_p = get_root(root_list, p)
        root_q = get_root(root_list, q)
        root_now = min(root_p, root_q, p)
        root_list[p] = root_now
        root_list[q] = root_now
        root_list[root_p] = root_now
        root_list[root_q] = root_now
    return root_list

def get_root(root_list, city):
    if root_list[city] == city:
        return city
    else: 
        root_list[city] = get_root(root_list, root_list[city])
        return root_list[city]

if __name__ == '__main__':
    N, K, L = map(int, input().split())
    roads = [None]*K
    rails = [None]*L
    for k in range(K):
        roads[k] = list(map(int, input().split()))
    for l in range(L):
        rails[l] = list(map(int, input().split()))
    
    
    '''N = 2*10**5
    L = int(N/2)
    K = int(N/2)
    roads = [None]*K
    rails = [None]*L
    for i in range(L):
        roads[i] = [2*i, 2*i+1]
    for i in range(K):
        rails[i] = [2*i, 2*i+1]'''
    
    road_roots = build_tree(N, roads)
    rail_roots = build_tree(N, rails)
    
    railroads = defaultdict(int)
    RR = []
    for n in range(N):
        rr = (get_root(road_roots, n), get_root(rail_roots, n))
        RR.append(rr)
        railroads[rr] += 1
    answer = [railroads[key] for key in RR]
    print(' '.join(map(str, answer)))

Submission status: Accepted

Solution code:
from collections import*;M=lambda:map(int,input().split());r=range;n,k,l=M()
def f(m):
  a=list(r(n))
  def g(i):
    if a[i]==i:return i
    a[i]=g(a[i]);return a[i]
  for _ in r(m):p,q=M();a[g(q-1)]=g(p-1)
  return g
x,y=f(k),f(l);c=Counter((x(i),y(i))for i in r(n));print(' '.join((str(c[x(i),y(i)])for i in r(n))))

Submission status: Accepted

Solution code:
from collections import*;M=lambda:map(int,input().split());n,k,l=M();d=[-1]*n;t=[-1]*n;r=range
def f(l,x):
  if l[x]<0:return x
  l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  if f(l,x)!=f(l,y):l[f(l,y)]=f(l,x)
for i in r(k+l):a,b=M();u(d if i<k else t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in r(n)];c=Counter(p);print(*[c[p[i]]for i in r(n)])

Submission status: Accepted

Solution code:
from collections import*;M=lambda:map(int,input().split());n,k,l=M();d=[-1]*n;t=[-1]*n;r=range
def f(l,x):
  if l[x]<0:return x
  else:l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  if f(l,x)!=f(l,y):l[f(l,y)]=f(l,x)
for i in r(k+l):a,b=M();u(d if i<k else t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in r(n)];c=Counter(p);print(*[c[p[i]]for i in r(n)])

Submission status: Accepted

Solution code:
from collections import*;M=lambda:map(int,input().split());n,k,l=M();d=[-1]*n;t=[-1]*n;r=range(n)
def f(l,x):
  if l[x]<0:return x
  else:l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  if f(l,x)!=f(l,y):l[f(l,y)]=f(l,x)
for i in range(k+l):a,b=M();u(d if i<k else t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in r];c=Counter(p);print(*[c[p[i]]for i in r])

Submission status: Accepted

Solution code:
from collections import*;M=lambda:map(int,input().split());n,k,l=M();d=[-1]*n;t=[-1]*n;r=range(n)
def f(l,x):
  if l[x]<0:return x
  else:l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  if f(l,x)!=f(l,y):l[f(l,y)]=f(l,x)
for _ in[0]*k:a,b=M();u(d,a-1,b-1)
for _ in[0]*l:a,b=M();u(t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in r];c=Counter(p);print(*[c[p[i]]for i in r])

Submission status: Accepted

Solution code:
from collections import*
n,k,l=map(int,input().split());d=[-1]*n;t=[-1]*n;M=lambda:map(int,input().split());r=range
def f(l,x):
  if l[x]<0:return x
  else:l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  if f(l,x)!=f(l,y):l[f(l,y)]=f(l,x)
for _ in r(k):a,b=M();u(d,a-1,b-1)
for _ in r(l):a,b=M();u(t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in r(n)];c=Counter(p);print(*[c[p[i]]for i in r(n)])

Submission status: Accepted

Solution code:
import collections
n,k,l=map(int,input().split());d=[-1]*n;t=[-1]*n
def f(l,x):
  if l[x]<0:return x
  else:l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  if f(l,x)!=f(l,y):l[f(l,y)]=f(l,x)
for _ in range(k):a,b=map(int,input().split());u(d,a-1,b-1)
for _ in range(l):a,b=map(int,input().split());u(t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in range(n)];c=collections.Counter(p);print(*[c[p[i]]for i in range(n)])

Submission status: Accepted

Solution code:
from collections import*
n,k,l=map(int,input().split());d=[-1]*n;t=[-1]*n
def f(l,x):
  if l[x]<0:return x
  else:l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  if f(l,x)!=f(l,y):l[f(l,y)]=f(l,x)
for _ in range(k):a,b=map(int,input().split());u(d,a-1,b-1)
for _ in range(l):a,b=map(int,input().split());u(t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in range(n)];c=Counter(p);print(*[c[p[i]]for i in range(n)])

Submission status: Accepted

Solution code:
from collections import*
n,k,l=map(int,input().split());d=[-1]*n;t=[-1]*n
def f(l,x):
  if l[x]<0:return x
  else:l[x]=f(l,l[x]);return l[x]
def u(l,x,y):
  x,y=f(l,x),f(l,y)
  if x!=y:l[y]=x
for _ in range(k):a,b=map(int,input().split());u(d,a-1,b-1)
for _ in range(l):a,b=map(int,input().split());u(t,a-1,b-1)
p=[(f(d,i),f(t,i))for i in range(n)];c=Counter(p);print(*[c[p[i]]for i in range(n)])

Submission status: Accepted

Solution code:
from collections import*
class u():
  def __init__(self,n):self.n,self.r=[-1]*n,[0]*n
  def f(self,x):
    if self.n[x]<0:return x
    else:self.n[x]=self.f(self.n[x]);return self.n[x]
  def u(self,x,y):
    x,y=self.f(x),self.f(y)
    if x==y:return
    elif self.r[x]>self.r[y]:self.n[x]+=self.n[y];self.n[y]=x
    else:self.n[y]+=self.n[x];self.n[x]=y;self.r[y]+=self.r[x]==self.r[y]
n,k,l=map(int,input().split());d=u(n);t=u(n)
for _ in range(k):a,b=map(int,input().split());d.u(a-1,b-1)
for _ in range(l):a,b=map(int,input().split());t.u(a-1,b-1)
p=[(d.f(i),t.f(i))for i in range(n)];c=Counter(p);print(*[c[p[i]]for i in range(n)])

Submission status: Accepted

Solution code:
from collections import*
class u():#UnionFind f-根探し u-連結 s-連結? c-要素数
  def __init__(self,n):self.n,self.r=[-1]*n,[0]*n
  def f(self,x):
    if self.n[x]<0:return x
    else:self.n[x]=self.f(self.n[x]);return self.n[x]
  def u(self,x,y):
    x,y=self.f(x),self.f(y)
    if x==y:return
    elif self.r[x]>self.r[y]:self.n[x]+=self.n[y];self.n[y]=x
    else:self.n[y]+=self.n[x];self.n[x]=y;self.r[y]+=self.r[x]==self.r[y]
  def s(self,x,y):return self.f(x)==self.f(y)
  def c(self,x):return -self.n[self.f(x)]
n,k,l=map(int,input().split())
d=u(n);t=u(n)
for _ in range(k):a,b=map(int,input().split());d.u(a-1,b-1)
for _ in range(l):a,b=map(int,input().split());t.u(a-1,b-1)
p=[(d.f(i),t.f(i))for i in range(n)]
c=Counter(p)
print(*[c[p[i]]for i in range(n)])

Submission status: Accepted

Solution code:
from collections import Counter

# UnionFind
class UnionFind():

    #0~Nまでの頂点数で初期化していることに注意
    def __init__(self, n):
        self.n = n
        self.root = [-1] * n

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

    def Unite(self, x, y):
        x = self.FindRoot(x)
        y = self.FindRoot(y)

        if x == y:
            return False
        if self.Size(x) < self.Size(y):
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

        return True

    def isSameGroup(self, x, y):
        return self.FindRoot(x) == self.FindRoot(y)

    def Size(self, x):
        return -self.root[self.FindRoot(x)]

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

Uni1 = UnionFind(N)

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

Uni2 = UnionFind(N)

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

pair = []
for i in range(N):
    pair.append((Uni1.FindRoot(i), Uni2.FindRoot(i)))

c = Counter(pair)
cnt = []
for i in range(N):
    cnt.append(c[pair[i]])

print(*cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a = ["a", "i", "u", "e", "o"]
    c = S()
    if c[0] in a:
        print("vowel")
    else:
        print("consonant")
    return

#B
def B():
    _ = II()
    t = LI()
    tsum = sum(t)
    for _ in range(II()):
        p, x = LI()
        print(tsum - t[p - 1] + x)
    return

#C
def C():
    s = input()
    lens = len(s)
    check = ["dream", "dreamer", "erase", "eraser"]
    q = deque()
    q.append(0)
    while q:
        p = q.pop()
        if p == lens:
            print("YES")
            return
        for i in check:
            if s[p:p + len(i)] == i:
                q.appendleft(p + len(i))
    print("NO")
    return

#D
def D():
    class UnionFind():

        def __init__(self, n):
            self.par = [i for i in range(n)]
            self.size = [1] * n
        
        def find(self, a):
            if a == self.par[a]:
                return a
            x = self.find(self.par[a])
            self.par[a] = x
            return x

        def unite(self, a, b):
            a = self.find(a)
            b = self.find(b)
            if a == b: return
            if a > b: a, b = b, a
            self.par[b] = a
            self.size[a] += self.size[b]

    n, k, l = LI()
    rail = UnionFind(n)
    road = UnionFind(n)

    for _ in range(k):
        p, q = LI_()
        rail.unite(p, q)
    for _ in range(l):
        r,s = LI_()
        road.unite(r, s)
    d = defaultdict(int)
    for i in range(n):
        d[(rail.find(i), road.find(i))] += 1
    for i in range(n):
        print(d[(rail.find(i), road.find(i))], end=" ")
    print()
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)
        
    def Find_root(self, x):
        if (self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        x = self.Find_root(x)
        y = self.Find_root(y)
        if (x == y):
            return
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if (self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_root(x) == self.Find_root(y)
    
    def Count(self, x):
        return - self.root[self.Find_root(x)]

import collections    
    
n, k, l = map(int, input().split())
union = UnionFind(n)
union1 = UnionFind(n)

for _ in range(k):
    p, q = map(int, input().split())
    union.Unite(p, q)
for _ in range(l):
    p, q = map(int, input().split())
    union1.Unite(p, q)

parents = [(union.Find_root(i), union1.Find_root(i)) for i in range(1, n + 1)]
lc = collections.Counter(parents)
ans = []
for i in range(n):
    ans.append(lc[parents[i]])
print(*ans)

Submission status: Accepted

Solution code:
import collections

class UnionFind:
    def __init__(self, n):
        self.parent = list(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 unite(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 are_same(self, x, y):
        return self.find(x) == self.find(y)


N, K, L = map(int, input().split())
uf1 = UnionFind(N)
for _ in range(K):
    x, y = map(int, input().split())
    uf1.unite(x, y)

uf2 = UnionFind(N)
for _ in range(L):
    x, y = map(int, input().split())
    uf2.unite(x, y)

parents = [(uf1.find(i), uf2.find(i)) for i in range(1, N+1)]
lc = collections.Counter(parents)
ans = []
for i in range(N):
    ans.append(lc[parents[i]])
print(*ans)

Submission status: Accepted

Solution code:
n,k,l=map(int,input().split())
pq=[list(map(int,input().split())) for _ in [0]*k]
rs=[list(map(int,input().split())) for _ in [0]*l]

gpq=[[] for _ in [0]*n]
[gpq[b-1].append(a-1) for a,b in pq]
[gpq[a-1].append(b-1) for a,b in pq]

grs=[[] for _ in [0]*n]
[grs[b-1].append(a-1) for a,b in rs]
[grs[a-1].append(b-1) for a,b in rs]

memo_set=set()
list_pq=[]
for i in range(n):
    if i not in memo_set:
        q=[i]
        temp_set={i}
        while q:
            qq=q.pop()
            for g in gpq[qq]:
                if g not in temp_set:
                    q.append(g)
                    temp_set.add(g)
                    memo_set.add(g)
        list_pq.append(temp_set)
        
memo_set=set()
list_rs=[]
for i in range(n):
    if i not in memo_set:
        q=[i]
        temp_set={i}
        while q:
            qq=q.pop()
            for g in grs[qq]:
                if g not in temp_set:
                    q.append(g)
                    temp_set.add(g)
                    memo_set.add(g)
        list_rs.append(temp_set)

dict_rs=dict()

for i,d in enumerate(list_rs):
    for j in d:
        dict_rs[j]=i

dict_pq=dict()

ans=[None]*n
for i,d in enumerate(list_pq):
    for j in d:
        no=dict_rs[j]
        if (i,no) in dict_pq.keys():
            ans[j]=dict_pq[(i,no)]
        else:
            a=len(d&list_rs[no])
            dict_pq[(i,no)]=a
            ans[j]=a

print(*ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC54 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

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

rank1 = [0]*(n)
rank2 = [0]*(n)

def find(x,i):
    if i == 1:
        if par1[x] == x:
            return x
        else:
            par1[x] = find(par1[x],i)
            return par1[x]
    else:
        if par2[x] == x:
            return x
        else:
            par2[x] = find(par2[x],i)
            return par2[x]

def union(x,y,i):
    x = find(x,i)
    y = find(y,i)
    if i == 1:
        if rank1[x] < rank1[y]:
            par1[x] = y
        else:
            par1[y] = x
            if rank1[x] == rank1[y]:
                rank1[x] += 1
    else:
        if rank2[x] < rank2[y]:
            par2[x] = y
        else:
            par2[y] = x
            if rank2[x] == rank2[y]:
                rank2[x] += 1

for _ in range(k):
    p,q = map(int,input().split())
    union(p-1,q-1,1)
for _ in range(l):
    r,s = map(int,input().split())
    union(r-1,s-1,2)

f = defaultdict(lambda : 0)
for i in range(n):
    x = (find(i,1),find(i,2))
    f[x] += 1
    
ans = []
for i in range(n):
    x = (find(i,1),find(i,2))
    ans.append(f[x])
print(*ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial



def union_r(node):
    global road_union
    if road_union[node] != node:
        road_union[node] = union_r(road_union[node])
    return road_union[node]

def union_t(node):
    global train_union
    if train_union[node] != node:
        train_union[node] = union_t(train_union[node])
    return train_union[node]


road_union, train_union = [], []


def main():
    node_num, road_num, train_num = map(int, input().split())

    global road_union
    road_union = [i for i in range(node_num + 1)]
    for i in range(road_num):
        a, b = map(int, input().split())
        parent_a = union_r(a)
        parent_b = union_r(b)
        road_union[min(parent_a, parent_b)] = max(parent_a, parent_b)
        # print(road_union)

    global train_union
    train_union = [i for i in range(node_num + 1)]
    for i in range(train_num):
        a, b = map(int, input().split())
        parent_a = union_t(a)
        parent_b = union_t(b)
        train_union[min(parent_a, parent_b)] = max(parent_a, parent_b)

    # print(train_union, road_union)

    ryouhou = [0 for i in range(node_num + 1)]
    for i in range(1, node_num + 1):
        parent_r = union_r(i)
        parent_t = union_t(i)
        ryouhou[i] = (parent_r, parent_t)

    # print(train_union, road_union, 'uuu')

    count_d = Counter(ryouhou)

    for i in range(1, node_num + 1):
        now_flg = ryouhou[i]
        print(count_d[now_flg], end=' ')
    print()





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial



def union_r(node):
    global road_union
    if road_union[node] != node:
        road_union[node] = union_r(road_union[node])
    return road_union[node]

def union_t(node):
    global train_union
    if train_union[node] != node:
        train_union[node] = union_t(train_union[node])
    return train_union[node]


road_union, train_union = [], []


def main():
    node_num, road_num, train_num = map(int, input().split())

    global road_union
    road_union = [i for i in range(node_num + 1)]
    for i in range(road_num):
        a, b = map(int, input().split())
        parent_a = union_r(a)
        parent_b = union_r(b)
        road_union[min(parent_a, parent_b)] = max(parent_a, parent_b)
        # print(road_union)

    global train_union
    train_union = [i for i in range(node_num + 1)]
    for i in range(train_num):
        a, b = map(int, input().split())
        parent_a = union_t(a)
        parent_b = union_t(b)
        train_union[min(parent_a, parent_b)] = max(parent_a, parent_b)

    # print(train_union, road_union)

    ryouhou = [0 for i in range(node_num + 1)]
    for i in range(1, node_num + 1):
        parent_r = union_r(i)
        parent_t = union_t(i)
        ryouhou[i] = (parent_r, parent_t)

    # print(train_union, road_union, 'uuu')

    count_d = Counter(ryouhou)

    for i in range(1, node_num + 1):
        now_flg = ryouhou[i]
        print(count_d[now_flg], end=' ')
    print()





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

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

N,K,L = II()
p,q = Line(K)
r,s = Line(L)

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

  def find(self, x):
    """
    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 と y のグループを結合
    """
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
      self.size[x] += self.size[y]

  def is_same(self, x, y):
    """
    x と y が同じグループか否か
    """
    return self.find(x) == self.find(y)

  def get_size(self, x):
    """
    x が属するグループの要素数
    """
    x = self.find(x)
    return self.size[x]
  
uf1 = UF(N)
uf2 = UF(N)
ans = []

for i in range(K):
  uf1.union(p[i]-1,q[i]-1)

for i in range(L):
  uf2.union(r[i]-1,s[i]-1)

x = []
for i in range(N):
  x.append([uf1.find(i), uf2.find(i)])
y = x[:]
y.sort(key=lambda x:(x[0],x[1]))

from bisect import bisect_left, bisect_right
for i in range(N):
  ans.append(bisect_right(y,x[i])- bisect_left(y,x[i]))

print(*ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

class UnionFindTree:

    def __init__(self, N):
        self.par = list(range(N))

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

    def union(self, a, b):
        a_root = self.find_root(a)
        b_root = self.find_root(b)
        self.par[a_root] = b_root
        return


def solve(N: int, K: int, L: int, p: "List[int]", q: "List[int]", r: "List[int]", s: "List[int]"):
    k_uf = UnionFindTree(N)
    l_uf = UnionFindTree(N)
    ret = [1] * N
    for i in range(K):
        k_uf.union(p[i] - 1, q[i] - 1)
    for i in range(L):
        l_uf.union(r[i] - 1, s[i] - 1)

    pars = []
    for i in range(N):
        pars.append((k_uf.find_root(i), l_uf.find_root(i), i))
    pars.sort()
    #print(pars)
    ret = [1] * N
    tmp = set()
    for i in range(1, N):
        if pars[i][0] == pars[i - 1][0] and pars[i][1] == pars[i - 1][1]:
            tmp.add(pars[i][2])
            tmp.add(pars[i - 1][2])
        else:
            cnt = len(tmp)
            for x in tmp:
                ret[x] = cnt
            tmp = set()
    for x in tmp:
        ret[x] = len(tmp)
    print(' '.join([str(r) for r in ret]))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    L = int(next(tokens))  # type: int
    p = [int()] * (K)  # type: "List[int]" 
    q = [int()] * (K)  # type: "List[int]" 
    for i in range(K):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    r = [int()] * (L)  # type: "List[int]" 
    s = [int()] * (L)  # type: "List[int]" 
    for i in range(L):
        r[i] = int(next(tokens))
        s[i] = int(next(tokens))
    solve(N, K, L, p, q, r, s)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

class UnionFind:
    def __init__(self,N):
        self.Parent = list(range(N))
    def get_Parent(self,n):
        if self.Parent[n] == n:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y: self.Parent[y] = x
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

N,K,L = map(int,input().split())
PQ = [list(map(int,input().split())) for _ in [0]*K]
RS = [list(map(int,input().split())) for _ in [0]*L]

T1 = UnionFind(N)
T2 = UnionFind(N)
for p,q in PQ:
    p-=1;q-=1
    T1.merge(p,q)
for r,s in RS:
    r-=1;s-=1
    T2.merge(r,s)
P = {}
for i in range(N):
    p = (T1.get_Parent(i),T2.get_Parent(i))
    if not p in P:P[p] = []
    P[p].append(i)

ans = [0]*N
for v in P.values():
    s = len(v)
    for i in v:
        ans[i] = s
print(*ans)