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

#print(N,K,L,D,T)

class UnionFind:
    def __init__(self, n: int) -> None:
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> None:
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        
    # 同じ集合に属するか判定
    #def same_check(self, x, y):
    #    return self.find(x) == self.find(y)

uf_D = UnionFind(N)
uf_T = UnionFind(N)

for d0, d1 in (map(int, input().split()) for _ in range(K)):
    uf_D.unite(d0-1, d1-1)
for d0, d1 in (map(int, input().split()) for _ in range(L)):
    uf_T.unite(d0-1, d1-1)

pairs = []
for i in range(N):
    pairs.append((uf_D.find(i), uf_T.find(i)))

pairs_count = {}
for p in pairs:
    if not p in pairs_count:
        pairs_count[p] = 1
    else:
        pairs_count[p] += 1

res = [0] * N
for i in range(N):
    res[i] = pairs_count[pairs[i]]
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

Submission status: Accepted

Solution code:
import sys
 
sys.setrecursionlimit(10000)

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

#print(N,K,L,D,T)

class UnionFind:
    def __init__(self, n: int) -> None:
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> None:
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        
    # 同じ集合に属するか判定
    #def same_check(self, x, y):
    #    return self.find(x) == self.find(y)

def uniteOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        d0 = d0 - 1
        d1 = d1 - 1
        uf.unite(d0, d1)

uf_D = UnionFind(N)
uf_T = UnionFind(N)

uniteOne(K, uf_D)
uniteOne(L, uf_T)


pairs = []
for i in range(N):
    pairs.append((uf_D.find(i), uf_T.find(i)))

pairs_count = {}
for p in pairs:
    if not p in pairs_count:
        pairs_count[p] = 1
    else:
        pairs_count[p] += 1

res = [0] * N
for i in range(N):
    res[i] = pairs_count[pairs[i]]
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

Submission status: Accepted

Solution code:
import sys
 
sys.setrecursionlimit(10000)

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

#print(N,K,L,D,T)

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

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

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        #if self.rank[x] < self.rank[y]:
        #    self.par[x] = y
        #else:
        #    self.par[y] = x
        #    if self.rank[x] == self.rank[y]:
        #        self.rank[x] += 1
        self.par[x] = y
        
    # 同じ集合に属するか判定
    #def same_check(self, x, y):
    #    return self.find(x) == self.find(y)

def execOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        d0 = d0 - 1
        d1 = d1 - 1
        uf.union(d0, d1)

uf_D = UnionFind(N)
uf_T = UnionFind(N)

execOne(K, uf_D)
execOne(L, uf_T)


pairs = []
for i in range(N):
    pairs.append((uf_D.find(i), uf_T.find(i)))

pairs_count = {}
for p in pairs:
    if not p in pairs_count:
        pairs_count[p] = 1
    else:
        pairs_count[p] += 1

res = [0] * N
for i in range(N):
    res[i] = pairs_count[pairs[i]]
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

Submission status: Accepted

Solution code:
import sys
 
sys.setrecursionlimit(10000)

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

#print(N,K,L,D,T)

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

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

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

def execOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        d0 = d0 - 1
        d1 = d1 - 1
        uf.union(d0, d1)

uf_D = UnionFind(N)
uf_T = UnionFind(N)

execOne(K, uf_D)
execOne(L, uf_T)


pairs = []
for i in range(N):
    pairs.append((uf_D.find(i), uf_T.find(i)))

pairs_count = {}
for p in pairs:
    if not p in pairs_count:
        pairs_count[p] = 1
    else:
        pairs_count[p] += 1

res = [0] * N
for i in range(N):
    res[i] = pairs_count[pairs[i]]
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

Submission status: Accepted

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

N,K,L=map(int,input().split())
R=[list(map(int,input().split())) for i in range(K)]
T=[list(map(int,input().split())) for i in range(L)]

Group1=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ
Group2=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ

def find1(x):#find(a)=find(b)のとき同じグループ
    while Group1[x] != x:
        x=Group1[x]
    return x

def Union1(x,y):#xとyが同じグループになるよう更新
    if find1(x) != find1(y):
        Group1[find1(y)]=Group1[find1(x)]=min(find1(y),find1(x))

def find2(x):#find(a)=find(b)のとき同じグループ
    while Group2[x] != x:
        x=Group2[x]
    return x

def Union2(x,y):#xとyが同じグループになるよう更新
    if find2(x) != find2(y):
        Group2[find2(y)]=Group2[find2(x)]=min(find2(y),find2(x))

for i,j in R:
    Union1(i,j)

for i,j in T:
    Union2(i,j)

from collections import defaultdict
ANS = defaultdict(int)

for i in range(1,N+1):
    ANS[(find1(i),find2(i))]+=1

for i in range(1,N+1):
    print(ANS[(find1(i),find2(i))])

Submission status: Accepted

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

sys.setrecursionlimit(10000)

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

import collections
import itertools
import operator

class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

    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)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]

ufk = UnionFind()
for i in range(K):
    a, b = (int(i) for i in input().split())
    ufk.unite(a, b)

ufl = UnionFind()
for i in range(L):
    a, b = (int(i) for i in input().split())
    ufl.unite(a, b)

L = []
for i in range(1,N+1):
    L.append( (ufk.find(i), ufl.find(i), i) )

def countList(L, ma = None):#maは要素の個数の最大値
    if ma == None:
        ma = len(L)
    L.sort() #すでにしているなら不要
    temp = (None, None, None)
    cc = 1
    reslis = [0] * (N+1)
    v = [L[0][2]]
    for se in L:
        if temp[0] == se[0] and temp[1] == se[1]:
            cc += 1
            v.append(se[2])
        else:
            if temp[0] == None:
                pass
            else:
                for aa in v:
                    reslis[aa] = cc
                v = [se[2]]
                cc = 1
            temp = se
    for aa in v:
        reslis[aa] = cc
    return reslis

reslis = countList(L, N)
reslis = reslis[1:]
reslis = [str(i) for i in reslis]
print(" ".join(reslis))

Submission status: Accepted

Solution code:
def root(parents, i):
    if parents[i] == i:
        return i
    parents[i] = root(parents, parents[i])
    return parents[i]


def main():
    n, k, l = map(int, input().split())
    roads = list(range(n))
    rails = list(range(n))

    for _ in range(k):
        a, b = map(lambda s: int(s) - 1, input().split())
        root_a, root_b = root(roads, a), root(roads, b)
        if root_a != root_b:
            roads[root_a] = root_b

    for _ in range(l):
        a, b = map(lambda s: int(s) - 1, input().split())
        root_a, root_b = root(rails, a), root(rails, b)
        if root_a != root_b:
            rails[root_a] = root_b

    counts = dict()
    for i in range(n):
        pair = (root(roads, i), root(rails, i))
        if not pair in counts:
            counts[pair] = 1
        else:
            counts[pair] += 1

    print(' '.join(
        map(lambda i: str(counts[(root(roads, i), root(rails, i))]), range(n))))


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = min(x, y)
        a[y] = a[x]


a_road = [i for i in range(N)]
for _ in range(K):
    p, q = [int(_) - 1 for _ in input().split()]
    unite(a_road, p, q)
a_railway = [i for i in range(N)]
for _ in range(L):
    r, s = [int(_) - 1 for _ in input().split()]
    unite(a_railway, r, s)
memo = {}
for i in range(N):
    memo[find(a_road, i), find(a_railway, i)] = memo.get(
        (find(a_road, i), find(a_railway, i)), 0) + 1

print(' '.join(str(memo[a_road[i], a_railway[i]]) for i in range(N)))

Submission status: Accepted

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


def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = max(x, y)
        a[y] = a[x]


a_road = [i for i in range(N)]
for _ in range(K):
    p, q = [int(_) - 1 for _ in input().split()]
    unite(a_road, p, q)
a_railway = [i for i in range(N)]
for _ in range(L):
    r, s = [int(_) - 1 for _ in input().split()]
    unite(a_railway, r, s)
memo = {}
for i in range(N):
    memo[find(a_road, i), find(a_railway, i)] = memo.get(
        (find(a_road, i), find(a_railway, i)), 0) + 1

print(' '.join(str(memo[find(a_road, i), find(a_railway, i)])
               for i in range(N)))

Submission status: Accepted

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

par = [i for i in range(2 * N)]
rank = [0] * (2 * N)


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


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

    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


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


for _ in range(K):
    p, q = [int(_) - 1 for _ in input().split()]
    unite(p, q)
for _ in range(L):
    r, s = [int(_) + N - 1 for _ in input().split()]
    unite(r, s)
memo = {}
for i in range(N):
    memo[find(i), find(i + N)] = memo.get(
        (find(i), find(i + N)), 0) + 1

print(' '.join(str(memo[find(i), find(i + N)])
               for i in range(N)))

Submission status: Accepted

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


class UFT():
    def __init__(self):
        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(self, x, y):
        return self.find(x) == self.find(y)


Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = {}
for i in range(1, N + 1):
    memo[Road.find(i) + N * Railway.find(i)] = memo.get(
        (Road.find(i) + N * Railway.find(i)), 0) + 1
print(' '.join(str(memo[Road.find(i) + N * Railway.find(i)])
               for i in range(1, N + 1)))

Submission status: Accepted

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


class UFT():
    def __init__(self):
        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(self, x, y):
        return self.find(x) == self.find(y)


Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = {}
for i in range(1, N + 1):
    memo[Road.find(i), Railway.find(i)] = memo.get(
        (Road.find(i), Railway.find(i)), 0) + 1
print(' '.join(str(memo[Road.find(i), Railway.find(i)])
               for i in range(1, N + 1)))

Submission status: Accepted

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


class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}
        for i in range(1, N + 1):
            self.par[i] = i
            self.rank[i] = 0

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


Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = {}
for i in range(1, N + 1):
    memo[Road.find(i), Railway.find(i)] = memo.get(
        (Road.find(i), Railway.find(i)), 0) + 1
print(' '.join(str(memo[Road.find(i), Railway.find(i)])
               for i in range(1, N + 1)))

Submission status: Accepted

Solution code:
from collections import defaultdict
class Unionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.rank=[0]*n

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

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
N,K,L=map(int,input().split())       
uf1=Unionfind(N)
uf2=Unionfind(N)
for i in range(K):
  p,q=map(int,input().split())
  uf1.unite(p-1,q-1)
for j in range(L):
  r,s=map(int,input().split())
  uf2.unite(r-1,s-1)
d=defaultdict(int)
ans=[0]*N
for i in range(N):
  d[(uf1.find(i),uf2.find(i))]+=1
for i in range(N):
  ans[i]=d[(uf1.find(i),uf2.find(i))]
print(" ".join(map(str,ans)))

Submission status: Accepted

Solution code:
from collections import defaultdict
class myUnionFind():
    def __init__(self,size):
        self.table = [-1 for i in range(size)]

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

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

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

N,K,L = map(int,input().split())
R,T = myUnionFind(N),myUnionFind(N)
for i in range(K):
    p,q = map(int,input().split())
    R.union(p-1,q-1)
for i in range(L):
    r,s = map(int,input().split())
    T.union(r-1,s-1)
both = defaultdict(int)
for i in range(N):
    both[(R.find(i),T.find(i))] += 1
ans = [both[(R.find(i),T.find(i))] for i in range(N)]
print(*ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)
def dps(gr,p,s,num):
    if gr[s]!=-1:
        return
    gr[s]=num
    for x in p[s]:
        dps(gr,p,x,num)

N,K,L=list(map(int,input().split()))
dic={}
road=[[] for _ in range(N)]
rail=[[] for _ in range(N)]

for i in range(K):
    p,q=list(map(int,input().split()))
    road[p-1].append(q-1)
    road[q-1].append(p-1)

for i in range(L):
    r,s=list(map(int,input().split()))
    rail[r-1].append(s-1)
    rail[s-1].append(r-1)


roadG=[-1 for _ in range(N)]
num=0
for i in range(N):
    if roadG[i]==-1:
        dps(roadG,road,i,num)
        num+=1

railG=[-1 for _ in range(N)]
num=0
for i in range(N):
    if railG[i]==-1:
        dps(railG,rail,i,num)
        num+=1
dic={}
arr=[]
for i in range(N):
    key=(roadG[i],railG[i])
    arr.append(key)
    dic[key]=dic.setdefault(key,0)+1
print(' '.join([str(dic[x]) for x in arr]))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)
def bps(gr,p,s,num):
    if gr[s]!=-1:
        return
    gr[s]=num
    for x in p[s]:
        bps(gr,p,x,num)

N,K,L=list(map(int,input().split()))
dic={}
road=[[] for _ in range(N)]
rail=[[] for _ in range(N)]

for i in range(K):
    p,q=list(map(int,input().split()))
    road[p-1].append(q-1)
    road[q-1].append(p-1)

for i in range(L):
    r,s=list(map(int,input().split()))
    rail[r-1].append(s-1)
    rail[s-1].append(r-1)


roadG=[-1 for _ in range(N)]
num=0
for i in range(N):
    if roadG[i]==-1:
        bps(roadG,road,i,num)
        num+=1

railG=[-1 for _ in range(N)]
num=0
for i in range(N):
    if railG[i]==-1:
        bps(railG,rail,i,num)
        num+=1
dic={}
arr=[]
for i in range(N):
    key=roadG[i]*N+railG[i]
    arr.append(key)
    dic[key]=dic.setdefault(key,0)+1
print(dic[arr[0]],end='')
for x in arr[1:]:
    print(' {}'.format(dic[x]),end='')
print('')

Submission status: Accepted

Solution code:
class UnionFind:
    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())
road = UnionFind(N)
railway = UnionFind(N)
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())
    railway.union(r-1,s-1)

from collections import defaultdict
d = defaultdict(lambda:0)

for i in range(N):
    p1,p2 = road.find(i),railway.find(i)
    d[(p1,p2)] += 1

ans = [str(d[(road.find(i),railway.find(i))]) for i in range(N)]
print(' '.join(ans))

Submission status: Accepted

Solution code:
#unionfind
class UF:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * 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 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
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
    def show(self):
        print(self.table)
    def data(self):
        res={}
        n=len(self.table)
        for i in range(n):
            res.update({i:[i] if self.table[i]<0 else [self.table[i]]})
        for i in range(n):
            res[res[i][0]]+=[i]
        for i in range(n):
            if len(res[i])==1:
                del res[i]
            else:
                del res[i][0]
        return list(res.values())

n,k,l=map(int,input().split())
pq=[list(map(int,input().split())) for _ in range(k)]
rs=[list(map(int,input().split())) for _ in range(l)]
auf=UF(n)
buf=UF(n)
for p,q in pq:
    auf.union(p-1,q-1)
for r,s in rs:
    buf.union(r-1,s-1)
key_list=[]
from collections import defaultdict
count=defaultdict(int)
for i in range(n):
    key=(auf._root(i),buf._root(i))
    key_list.append(key)
    count[key]+=1
ans=[0 for _ in range(n)]
for i,key in enumerate(key_list):
    ans[i]=str(count[key])
print(" ".join(ans))

Submission status: Accepted

Solution code:

#Union-Find木の構築
import sys
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

    def buildTree(a):
        #aT = [0]*(iN+1)
        aT = list(range(iN+1))
        for p,q in a:
            rp = getRoot(aT,p)
            rq = getRoot(aT,q)
            thisRoot = max(rp,rq,q) #みんな小さい方に合わせてるのでデカい方に合>わせてみる
            aT[p] = thisRoot
            aT[q] = thisRoot
            aT[rp] = thisRoot #これで Union してるつもり
            aT[rq] = thisRoot
        return aT
    def getRoot(a,i): #find
        #if a[i] == i or a[i] == 0:
        #   if a[i] == 0 : a[i] = i
        if a[i] == i :
            return i
    #   elif i < a[i] :
        else :
            a[i] = getRoot(a,a[i])
            return a[i]
    #   else:
    #       print("! ",i,a[i])

    aT道 = buildTree(aD[0:iK])
    aT鉄道 = buildTree(aD[iK:])
    aRet = []
    dRet = {}
    for i in range(1,iN+1):
        # いやはやこんなもんもキーになるのか。
        Comb = (getRoot(aT道,i), getRoot(aT鉄道,i))
        aRet.append(Comb)
        if Comb in dRet:
            dRet[Comb] += 1
        else:
            dRet[Comb] = 1
    print(" ".join([str(dRet[_]) for _ in aRet]))

解()

Submission status: Accepted

Solution code:
#Union-Find木の構築
import sys
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

    def buildTree(a):
        #aT = [0]*(iN+1)
        aT = list(range(iN+1))
        for p,q in a:
            rp = getRoot(aT,p)
            rq = getRoot(aT,q)
            thisRoot = max(rp,rq,q)
            aT[p] = thisRoot
            aT[q] = thisRoot
            aT[rp] = thisRoot #これで Union してるつもり
            aT[rq] = thisRoot
        return aT
    def getRoot(a,i): #find みんな小さい方に合わせるならデカい方に合わせてみよう
        #if a[i] == i or a[i] == 0:
        #   if a[i] == 0 : a[i] = i
        if a[i] == i :
            return i
        elif i < a[i] :
            a[i] = getRoot(a,a[i])
            return a[i]
    #   else:
    #       print("! ",i,a[i])

    aT道 = buildTree(aD[0:iK])
    aT鉄道 = buildTree(aD[iK:])
    aRet = []
    dRet = {}
    for i in range(1,iN+1):
        # いやはやこんなもんもキーになるのか。
        Comb = (getRoot(aT道,i), getRoot(aT鉄道,i))
        aRet.append(Comb)
        if Comb in dRet:
            dRet[Comb] += 1
        else:
            dRet[Comb] = 1
    print(" ".join([str(dRet[_]) for _ in aRet]))

解()

Submission status: Accepted

Solution code:
#Union-Find木の構築
import sys
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

    def buildTree(a):
        aT = [0]*(iN+1)
        for p,q in a:
            rp = getRoot(aT,p)
            rq = getRoot(aT,q)
            thisRoot = max(rp,rq,q)
            aT[p] = thisRoot
            aT[q] = thisRoot
            aT[rp] = thisRoot #これで Union してるつもり
            aT[rq] = thisRoot
        return aT
    def getRoot(a,i): #find みんな小さい方に合わせるならデカい方に合わせてみよう
        if a[i] == i or a[i] == 0:
            if a[i] == 0 : a[i] = i
            return i
        elif i < a[i] :
            a[i] = getRoot(a,a[i])
            return a[i]
    #   else:
    #       print("! ",i,a[i])

    aT道 = buildTree(aD[0:iK])
    aT鉄道 = buildTree(aD[iK:])
    aRet = []
    dRet = {}
    for i in range(1,iN+1):
        # いやはやこんなもんもキーになるのか。
        Comb = (getRoot(aT道,i), getRoot(aT鉄道,i))
        aRet.append(Comb)
        if Comb in dRet:
            dRet[Comb] += 1
        else:
            dRet[Comb] = 1
    print(" ".join([str(dRet[_]) for _ in aRet]))

解()

Submission status: Accepted

Solution code:
def Parent(i, A = list):
    if i == A[i]:
        return i
    else:
        return Parent(A[i], A)

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

#数字の小さい方を親ノードとする
Road = [int(_) for _ in range(N)]
Rail = [int(_) for _ in range(N)]
for i in range(K):
    p, q = map(int, input().split())
    p, q = p-1, q-1
    pP, qP = Parent(p, Road), Parent(q, Road)
    if pP <= qP:
        Road[qP] = pP
    else:
        Road[pP] = qP
for i in range(L):
    r, s = map(int, input().split())
    r, s = r-1, s-1
    rP, sP = Parent(r, Rail), Parent(s, Rail)
    if rP <= sP:
        Rail[sP] = rP
    else:
        Rail[rP] = sP

Parents, Count = [], {}
for i in range(N):
    roadP, railP = Parent(i, Road), Parent(i, Rail)
    Parents.append((roadP, railP))
    if (roadP, railP) in Count:
        Count[(roadP, railP)] += 1
    else:
        Count[(roadP, railP)] = 1

Ans = []
for i in range(N):
    Ans.append(Count[Parents[i]])
print(" ".join(map(str, Ans)))

Submission status: Accepted

Solution code:
from collections import defaultdict
def find(x, A): #unionfind
    p = A[x]
    if p == x:
        return x
    a = find(p, A)
    A[x] = a
    return a

N, K, L = map( int, input().split())
V = [ i for i in range(N)]
W = [ i for i in range(N)]
for _ in range(K):
    p, q = map( int, input().split())
    p, q = p-1, q-1
    bp, bq = find(p,V), find(q,V)
    V[q] = bp
    V[bq] = bp

for _ in range(L):
    r, s = map( int, input().split())
    r, s = r-1, s-1
    br, bs = find(r,W), find(s,W)
    W[s] = br
    W[bs] = br

d = defaultdict(int) #デフォルトで0を返す。
for i in range(N):
    d[(find(i,V), find(i, W))] += 1
ANS = [0]*N
for i in range(N):
    ANS[i] = d[(find(i,V), find(i, W))]

print(' '.join( map( str, ANS)))

Submission status: Accepted

Solution code:
from collections import defaultdict
def find(x, A):
    p = A[x]
    if p == x:
        return x
    a = find(p, A)
    A[x] = a
    find(a,A)
    return a

N, K, L = map( int, input().split())
V = [ i for i in range(N)]
W = [ i for i in range(N)]
for _ in range(K):
    p, q = map( int, input().split())
    p, q = p-1, q-1
    bp, bq = find(p,V), find(q,V)
    V[q] = bp
    V[bq] = bp

for _ in range(L):
    r, s = map( int, input().split())
    r, s = r-1, s-1
    br, bs = find(r,W), find(s,W)
    W[s] = br
    W[bs] = br

d = defaultdict(int)
for i in range(N):
    d[(find(i,V), find(i, W))] += 1
ANS = [0]*N
for i in range(N):
    ANS[i] = d[(find(i,V), find(i, W))]

print(' '.join( map( str, ANS)))