Problem:


Score : 400 points

Problem Statement

There are N cities. There are also K roads and L railways, extending between the cities.
The i-th road bidirectionally connects the p_i-th and q_i-th cities, and the i-th railway bidirectionally connects the r_i-th and s_i-th cities.
No two roads connect the same pair of cities. Similarly, no two railways connect the same pair of cities.

We will say city A and B are connected by roads if city B is reachable from city A by traversing some number of roads. Here, any city is considered to be connected to itself by roads.
We will also define connectivity by railways similarly.

For each city, find the number of the cities connected to that city by both roads and railways.

Constraints

2 ≦ N ≦ 2*10^5

1 ≦ K, L≦ 10^5

1 ≦ p_i, q_i, r_i, s_i ≦ N

p_i < q_i

r_i < s_i

When i ≠ j, (p_i, q_i) ≠ (p_j, q_j)

When i ≠ j, (r_i, s_i) ≠ (r_j, s_j)

Input

The input is given from Standard Input in the following format:

N K L
p_1 q_1
:
p_K q_K
r_1 s_1
:
r_L s_L

Output

Print N integers. The i-th of them should represent the number of the cities connected to the i-th city by both roads and railways.

Sample Input 1

4 3 1
1 2
2 3
3 4
2 3

Sample Output 1

1 2 2 1

All the four cities are connected to each other by roads.

By railways, only the second and third cities are connected. Thus, the answers for the cities are 1, 2, 2 and 1, respectively.

Sample Input 2

4 2 2
1 2
2 3
1 4
2 3

Sample Output 2

1 2 2 1

Sample Input 3

7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7

Sample Output 3

1 1 2 1 2 2 2



Sample input:
4 3 1
1 2
2 3
3 4
2 3


Sample output:
1 2 2 1

Submission status: Accepted

Solution code:
import sys
from collections import deque, Counter
sys.setrecursionlimit(1000000)
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)]

G_r = [[] for _ in range(N+1)]
for elem in pq:
    G_r[elem[0]].append(elem[1])
    G_r[elem[1]].append(elem[0])
G_t = [[] for _ in range(N+1)]
for elem in rs:
    G_t[elem[0]].append(elem[1])
    G_t[elem[1]].append(elem[0])


field_r = [None]*(N+1)


def dfs_r(i, idx):
    q = deque()
    q.append(i)
    field_r[i] = idx
    while q:
        tmp = q.pop()
        for pos in G_r[tmp]:
            if field_r[pos] is None:
                field_r[pos] = idx
                q.append(pos)
            else:
                continue
idx = 0
for i in range(1, N+1):
    if field_r[i] is None:
        dfs_r(i, idx)
        idx += 1


field_t = [None]*(N+1)


def dfs_t(i, idx):
    q = deque()
    q.append(i)
    field_t[i] = idx
    while q:
        tmp = q.pop()
        for pos in G_t[tmp]:
            if field_t[pos] is None:
                field_t[pos] = idx
                q.append(pos)
            else:
                continue
idx = 0
for i in range(1, N+1):
    if field_t[i] is None:
        dfs_t(i, idx)
        idx += 1

m = list(zip(field_r[1:], field_t[1:]))
cnt = Counter(m)
ans = []
for elem in list(m):
    ans.append(cnt[elem])
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
            if self.par[rx] > self.par[ry]:
                self.par[rx] = ry
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
        return

N, K, L = inpl()
ufk = UnionFind(N)
for i in range(K):
    p, q = inpl()
    ufk.union(p-1, q-1)

ufr = UnionFind(N)
for i in range(L):
    r, s = inpl()
    ufr.union(r-1, s-1)

from collections import defaultdict
ans = defaultdict(lambda: 0)
for i in range(N):
    ans[ufk.find(i),ufr.find(i)] +=1
Ans = [0 for _ in range(N)]
for i in range(N):
    Ans[i] = ans[ufk.find(i),ufr.find(i)]
print(*Ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            #print("x and y has already united")
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
                
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
from collections import defaultdict
    
n,k,l = li()
pq = []
rs = []

for _ in range(k):
    pq.append(tuple(li_()))
    
for _ in range(l):
    rs.append(tuple(li_()))

road = UnionFind(n)
rail = UnionFind(n)

for p,q in pq:
    road.unite(p,q)
    
for r,s in rs:
    rail.unite(r,s)
    
for i in range(n):
    road.find(i)
    
for i in range(n):
    rail.find(i)
    
road_dic = {i:set() for i in range(n)}
rail_dic = {i:set() for i in range(n)}

for i in range(n):
    road_dic[road.par[i]].add(i)
    rail_dic[rail.par[i]].add(i)
    
ans_dic = defaultdict(int)
for i in range(n):
    if ans_dic[(road.par[i], rail.par[i])] == 0:
        ans_dic[(road.par[i], rail.par[i])] = len(road_dic[road.par[i]] & rail_dic[rail.par[i]])
    
ans = []
for i in range(n):
    ans.append(ans_dic[(road.par[i], rail.par[i])])
    
print(*ans)

Submission status: Accepted

Solution code:
from collections import Counter
N,K,L = map(int,input().split())
P = [tuple(map(int,input().split())) for i in range(K)]
R = [tuple(map(int,input().split())) for i in range(L)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf1 = UnionFind(N)
for p,q in P:
    p,q = p-1,q-1
    if uf1.is_same(p,q): continue
    uf1.unite(p,q)

uf2 = UnionFind(N)
for r,s in R:
    r,s = r-1,s-1
    if uf2.is_same(r,s): continue
    uf2.unite(r,s)

pairs = Counter()
for i in range(N):
    a = uf1.root(i)
    b = uf2.root(i)
    pairs[(a,b)] += 1

ans = []
for i in range(N):
    a = uf1.root(i)
    b = uf2.root(i)
    ans.append(pairs[(a,b)])
print(*ans)

Submission status: Accepted

Solution code:
# Union-Findデータ構造
class UnionFind:
    def __init__(self, numV):
        self.pars = [i for i in range(numV)]
        self.ranks = [0] * numV

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1


N, K, L = map(int, input().split())
pqs = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(K)]
rss = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(L)]

# 道路
UFRoad = UnionFind(N)
for p, q in pqs:
    UFRoad.union(p, q)

# 鉄道
UFRailway = UnionFind(N)
for r, s in rss:
    UFRailway.union(r, s)

Ts = [(UFRoad.find(i), UFRailway.find(i), i) for i in range(N)] + [(N, N, N)]
Ts.sort()

anss = [0] * N
iFr = 0
for i in range(N):
    if Ts[i][0:2] != Ts[i + 1][0:2]:
        for j in range(iFr, i + 1):
            anss[Ts[j][2]] = i - iFr + 1
        iFr = i + 1

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(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 x<y:
            self.par[y] = x
        else:
            self.par[x] = y
    def same(self, x, y):
        return self.find(x) == self.find(y)


n,k,l = map(int, input().split())
pq = UnionFind(n)
for _ in range(k):
    p,q = map(int, input().split())
    pq.unite(p-1,q-1)
rs = UnionFind(n)
for _ in range(l):
    r,s = map(int, input().split())
    rs.unite(r-1,s-1)

# print(pq.par)
# print(rs.par)
d = {}
for x in range(n):
    a = pq.find(x)
    b = rs.find(x)
    if (a,b) not in d:
        d[(a,b)] = 0
    d[(a,b)] += 1
# print(d)
ret = []
for x in range(n):
    a = pq.find(x)
    b = rs.find(x)
    ret.append(str(d[(a,b)]))

print(" ".join(ret  ))

Submission status: Accepted

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

def main():
    n, k, l = map(int, input().split())
    pq = get_edges(k)
    rs = get_edges(l)
    road_groups = get_group(n, pq)
    rail_groups = get_group(n, rs)
    count = {}
    for i in range(n):
        gp = (find(i, road_groups), find(i, rail_groups))
        if gp not in count:
            count[gp] = 1
        else:
            count[gp] += 1
    res = []
    for i in range(n):
        gp = (find(i, road_groups), find(i, rail_groups))
        res.append(count[gp])
    print(" ".join(map(str, res)))

def get_edges(k):
    pq = []
    for i in range(k):
        p1, q1 = map(int, input().split())
        pq.append((p1 - 1, q1 - 1))
    return pq

def get_group(n, edges):
    group = [i for i in range(n)]
    for x, y in edges:
        unite(x, y, group)
    return group

def unite(x, y, parents):
    px = find(x, parents)
    py = find(y, parents)
    parents[py] = px

def find(x, parents):
    if parents[x] == x:
        return x
    fx = find(parents[x], parents)
    parents[x] = fx
    return fx

main()

Submission status: Accepted

Solution code:
from collections import Counter

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

def unite(par, x, y):
    rx, ry = root(par, x), root(par, y)
    if rx == ry:
        return

    if rank[rx] > rank[ry]:
        par[ry] = rx
    elif rank[rx] < rank[ry]:
        par[rx] = ry
    else:
        par[ry] = rx
        rank[rx] += 1
        
N, K, L = map(int, input().split())

rank = [1] * N
roads = [i for i in range(N)]
for _ in range(K):
    unite(roads, *map(lambda x: int(x) - 1, input().split()))

rank = [1] * N
rails = [i for i in range(N)]
for _ in range(L):
    unite(rails, *map(lambda x: int(x) - 1, input().split()))

count = Counter((root(roads, i), root(rails, i)) for i in range(N))
print(*(count[root(roads, i), root(rails, i)] for i in range(N)))

Submission status: Accepted

Solution code:
f = lambda: list(map(int,input().split()))
f_ = lambda: [int(x)-1 for x in input().split()]


class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

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

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

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[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)


n,k,l = f()
ud = UnionFind(n)
for _ in range(k):
    p,q = f_()
    ud.unite(p,q)
ut = UnionFind(n)
for _ in range(l):
    p,q = f_()
    ut.unite(p,q)

p = [(ud.find(i),ut.find(i)) for i in range(n)]

from collections import Counter
c = Counter(p)
print(*[c[p[i]] for i in range(n)])

Submission status: Accepted

Solution code:
N,K,L=map(int,input().split())
G=[[] for i in range(N)]
H=[[] for i in range(N)]
#T=[-1 for i in range(N)]
#B=[-1 for i in range(N)]
for i in range(K):
    p,q=map(int,input().split())
    G[p-1].append(q-1)
    G[q-1].append(p-1)
for i in range(L):
    r,s=map(int,input().split())
    H[r-1].append(s-1)
    H[s-1].append(r-1)
def dfs(A):
    k=1
    q=[]
    reached=[0 for i in range(N)]
    res=[0 for i in range(N)]
    for i in range(N):
        if reached[i]==1:
            continue
        q.append(i)
        while(len(q)>0):
            r=q[-1]
            q.pop()
            res[r]=k
            for p in A[r]:
                if reached[p]==1:
                    continue
                q.append(p)
                reached[p]=1
        k+=1
    return res
T=dfs(G)
B=dfs(H)
TB=[(T[i],B[i]) for i in range(N)]
D=dict()
for i in range(N):
    if TB[i] in D:
        D[TB[i]]+=1
    else:
        D[TB[i]]=1
ans=[str(D[TB[i]]) for i in range(N)]
print(" ".join(ans))

Submission status: Accepted

Solution code:
N,K,L=map(int,input().split())
G=[[] for i in range(N)]
H=[[] for i in range(N)]
#T=[-1 for i in range(N)]
#B=[-1 for i in range(N)]
for i in range(K):
    p,q=map(int,input().split())
    G[p-1].append(q-1)
    G[q-1].append(p-1)
for i in range(L):
    r,s=map(int,input().split())
    H[r-1].append(s-1)
    H[s-1].append(r-1)
def bfs(A):
    k=1
    q=[]
    reached=[0 for i in range(N)]
    res=[0 for i in range(N)]
    for i in range(N):
        if reached[i]==1:
            continue
        q.append(i)
        while(len(q)>0):
            r=q[-1]
            q.pop()
            res[r]=k
            for p in A[r]:
                if reached[p]==1:
                    continue
                q.append(p)
                reached[p]=1
        k+=1
    return res
T=bfs(G)
B=bfs(H)
TB=[(T[i],B[i]) for i in range(N)]
D=dict()
for i in range(N):
    if TB[i] in D:
        D[TB[i]]+=1
    else:
        D[TB[i]]=1
ans=[str(D[TB[i]]) for i in range(N)]
print(" ".join(ans))

Submission status: Accepted

Solution code:
from collections import deque

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

G = [[[] for j in range(N)] for i in range(2)]
check = [[0 for l in range(N)] for k in range(2)]


def bfs(s, cnt, mode):
    q = deque()
    q.append(s)
    check[mode][s] = cnt

    while len(q) != 0:
        u = q.popleft()
        for i in G[mode][u]:
            if check[mode][i] == 0:
                q.append(i)
                check[mode][i] = cnt


def main():
    for i in range(K):
        p, q = map(int, input().split())
        G[0][p-1].append(q-1)
        G[0][q-1].append(p-1)
    for i in range(L):
        r, s = map(int, input().split())
        G[1][r-1].append(s-1)
        G[1][s-1].append(r-1)

    cnt = 1
    for i in range(N):
        if check[0][i] == 0:
            bfs(i, cnt, 0)
            cnt += 1

    cnt = 1
    for i in range(N):
        if check[1][i] == 0:
            bfs(i, cnt, 1)
            cnt += 1

    groups = {}
    for i in range(N):
        a, b = check[0][i], check[1][i]
        groups[(a, b)] = groups.get((a, b), 0) + 1

    nums = []
    for i in range(N):
        a, b = check[0][i], check[1][i]
        nums.append(str(groups[(a, b)]))

    print(" ".join(nums))


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

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

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF1 = UnionFind(N)
UF2 = UnionFind(N)

for k in range(K):
    p, q = map(int, input().split())
    p, q = p-1, q-1
    UF1.union(p, q)
for l in range(L):
    r, s = map(int, input().split())
    r, s = r-1, s-1
    UF2.union(r, s)

UF1.all_find()
UF2.all_find()

D = defaultdict(int)
for p1, p2 in zip(UF1.par, UF2.par):
    D[(p1, p2)] += 1

ans = [D[(p1, p2)] for p1, p2 in zip(UF1.par, UF2.par)]
print(*ans)

Submission status: Accepted

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


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

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

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF1 = UnionFind(N)
UF2 = UnionFind(N)

for k in range(K):
    p, q = map(int, input().split())
    UF1.union(p-1, q-1)

for l in range(L):
    r, s = map(int, input().split())
    UF2.union(r-1, s-1)

UF1.all_find()
UF2.all_find()

D = defaultdict(int)
for i in range(N):
    D[UF1.par[i], UF2.par[i]] += 1

ans = [D[UF1.par[i], UF2.par[i]] for i in range(N)]
print(*ans)

Submission status: Accepted

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


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

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

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF1 = UnionFind(N)
UF2 = UnionFind(N)
for k in range(K):
    p, q = map(int, input().split())
    UF1.union(p-1, q-1)

for l in range(L):
    l, s = map(int, input().split())
    UF2.union(l-1, s-1)

UF1.all_find()
UF2.all_find()

D = defaultdict(int)
for i in range(N):
    D[UF1.par[i], UF2.par[i]] += 1

ans = [D[UF1.par[i], UF2.par[i]] for i in range(N)]
print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

class UnionFind(object):
  def __init__(self,n):
    self.table=[-1]*n
 
  def find(self,x):
    parent=self.table[x]
    if parent<0:
      return x
    else:
      root=self.find(parent)
      self.table[x]=root
      return root
 
  def union(self,a,b):
    root1=self.find(a)
    root2=self.find(b)
    if root1 != root2:
      if self.table[root1] != self.table[root2]:
        if self.table[root1] < self.table[root2]:
          self.table[root2]=root1
        else:
          self.table[root1]=root2
      else:
        self.table[root1]+=(-1)
        self.table[root2]=root1
      
ufK=UnionFind(N)
for i in range(K):
  p,q=map(int,input().split())
  ufK.union(p-1,q-1)

ufL=UnionFind(N)
for i in range(L):
  p,q=map(int,input().split())
  ufL.union(p-1,q-1)

KL=defaultdict(int)
ans=[]
for i in range(N):
  a=ufK.find(i)
  b=ufL.find(i)
  KL[(a,b)]+=1
for i in range(N):
  a=ufK.find(i)
  b=ufL.find(i)
  ans.append(KL[(a,b)])
  
print(*ans)

Submission status: Accepted

Solution code:
n, k, l = map(int, raw_input().split())

def rr(x, gr):
    if x != gr[x]: gr[x] = x = rr(gr[x], gr)
    return x

def g(x, y, gr):
    px = rr(x, gr)
    py = rr(y, gr)
    if px < py:
        gr[py] = px
    else:
        gr[px] = py

roads = range(n)
for _ in range(k):
    p, q = map(int, raw_input().split())
    g(p - 1, q - 1, roads)
for i in range(n): rr(i, roads)

rails = range(n)
for _ in range(l):
    r, s = map(int, raw_input().split())
    g(r - 1, s - 1, rails)
for i in range(n): rr(i, rails)

c = {}
for p1, p2 in zip(roads, rails):
    try:
        c[p1, p2] += 1
    except KeyError:
        c[p1, p2] = 1

ans = [c[p1, p2] for p1, p2 in zip(roads, rails)]
print ' '.join(map(str, ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
def inpl(): return tuple(map(int, input().split()))
 
N, K, L = inpl()
 
tree = [[[-1, 1]  for _ in range(N+1)] for _ in range(2)] # [next, rank]

def find(i, t):
    if tree[t][i][0] == -1:
        group = i
    else:
        group = find(tree[t][i][0], t)
        tree[t][i][0] = group
    return group
 
def unite(x, y, t):
    px = find(x, t)
    py = find(y, t)
     
    if tree[t][px][1] == tree[t][py][1]: # rank is same
        tree[t][py][0] = px
        tree[t][px][1] += 1
    else:
        if tree[t][px][1] < tree[t][py][1]:
            px, py = py, px
        tree[t][py][0] = px
 
for _ in range(K):
    x, y = inpl()
    if not int(find(x, 0) == find(y, 0)):
        unite(x, y, 0)

for _ in range(L):
    x, y = inpl()
    if not int(find(x, 1) == find(y, 1)):
        unite(x, y, 1)

D = defaultdict(lambda: 0)
P = []
for i in range(1, N+1):
    a, b = find(i, 0), find(i, 1)
    D[(a, b)] += 1
    P.append((a, b))
print(" ".join(map(str, [D[(a, b)] for a, b in P])))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n): 
        self.par = [-1]*n
        
    def __repr__(self):
        return "union_find({0})".format(self.par)
        
    def unite(self, x, y):
        if self.root(x) != self.root(y):
            self.par[self.root(x)] = y
        
    def root(self, x):
        if self.par[x] == -1:
            return x
        else:
            self.par[x] = self.root(self.par[x])
        return self.par[x]
        
    def same(self, x, y):
        return self.root(x) == self.root(y)
        
        
from sys import stdin
def readLine_int_list():return list(map(int, stdin.readline().split()))
from collections import defaultdict

def main():
    n,k,l = readLine_int_list()
    
    rail = UnionFind(n)
    road = UnionFind(n)
    
    for _ in range(k):
        p, q = readLine_int_list()
        p, q = p-1, q-1
        road.unite(p, q)
     
    for _ in range(l):
        p, q = readLine_int_list()
        p, q = p-1, q-1
        rail.unite(p, q)
        
    d = defaultdict(int)
    
    for i in range(n):
        d[road.root(i), rail.root(i)] += 1
    results = (d[road.root(i), rail.root(i)] for i in range(n))


    print(" ".join(str(n) for n in results))
    

if __name__ == "__main__":main()

Submission status: Accepted

Solution code:
# 頂点 v の所属するグループを調べる
def root(v, uni):
  if uni[v] < 0:  # v が親の場合
    return v
  else:           # v が子の場合
    uni[v] = root(uni[v], uni)  # 親のrootを調べる
    return uni[v]

# 頂点 a と頂点 b をつなぐ。もともと同じグループのとき、False を返す
def connect(a, b, uni):
  # まずはそれぞれ根の番号に置き換える
  ra = root(a, uni)
  rb = root(b, uni)
  if ra == rb:  # a と b がそもそも同じグループに属しているなら即終了
    return False
	
  # ra を大きなグループにしたいので、逆であれば入れ替える
  if uni[ra] > uni[rb]: # rbの方が要素数が多ければ
    tmp = ra
    ra  = rb 
    rb  = tmp

  # ra と rb を結合し、rb の親を ra とする
  uni[ra] += uni[rb]
  uni[rb] = ra
  return True
      
##
N, K, L = map(int, input().split())

road = [-1]*(N+1)
rail = [-1]*(N+1)

for i in range(K):
  a, b = map(int, input().split())
  connect(a, b, road)

for i in range(L):
  a, b = map(int, input().split())
  connect(a, b, rail)


##
dp = [0]*(N+1)
for i in range(1, N+1):
  dp[i] = (root(i, road), root(i, rail))

dic = {}
for i in range(1, N+1):
  key = dp[i]
  if key not in dic:
    dic[key] = 1
  else:
    dic[key] += 1

for i in range(1, N+1):
  ans = dic[dp[i]]
  if i == N:
    print(ans)
  else:
    print(ans, end=" ")

Submission status: Accepted

Solution code:
from collections import defaultdict
class UnionFind:
    def __init__(self, size):
        self.rank = [0] * size
        self.par = range(size)

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

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

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

        if (self.rank[x] > self.rank[y]):
            self.par[y] = x
        else:
            self.par[x] = y
            if (self.rank[x] == self.rank[y]): self.rank[y] += 1

N, K, L = map(int, raw_input().split())
pq = [map(int, raw_input().split()) for i in xrange(K)]
rs = [map(int, raw_input().split()) for i in xrange(L)]

road = UnionFind(N)
rail = UnionFind(N)
for p, q in pq:
    road.unite(p - 1, q - 1)
for r, s in rs:
    rail.unite(r - 1, s - 1)

for i in xrange(N):
    road.find(i)
    rail.find(i)

pair = defaultdict(int) 
for i, j in zip(road.par, rail.par):
    pair[i, j] += 1

print " ".join(map(str, [pair[road.par[i], rail.par[i]] for i in xrange(N)]))

Submission status: Accepted

Solution code:
import sys
from collections import Counter

class UnionFind:

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

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

        return self.p[x]

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

    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)

        if u == v:
            return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
        else:
            self.p[v] = u

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1


N, K, L = map(int, sys.stdin.readline().split())

uf1 = UnionFind(N)
uf2 = UnionFind(N)

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

for i in range(L):
    r, s = map(int, sys.stdin.readline().split())
    r, s = r - 1, s - 1
    uf2.unite(r, s)

cntr = Counter()

for i in range(N):
    u = uf1.find_root(i)
    v = uf2.find_root(i)

    cntr[(u, v)] += 1

ans = []

for i in range(N):
    u = uf1.find_root(i)
    v = uf2.find_root(i)

    ans.append(cntr[(u, v)])

print(*ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7


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

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    n,k,l = list(map(int, input().split()))
    uk = UnionFind(n)
    ul = UnionFind(n)
    for _ in range(k):
        p,q = list(map(int, input().split()))
        uk.union(p-1,q-1)
    for _ in range(l):
        p,q = list(map(int, input().split()))
        ul.union(p-1,q-1)

    sk = collections.defaultdict(set)
    sl = collections.defaultdict(set)
    m = {}

    for i in range(n):
        sk[uk.find(i)].add(i)
        sl[ul.find(i)].add(i)
    r = []
    for i in range(n):
        if i in m:
            r.append(m[i])
            continue
        ss = sk[uk.find(i)] & sl[ul.find(i)]
        ssl = len(ss)
        for sc in ss:
            m[sc] = ssl
        r.append(m[i])

    return " ".join(map(str, r))



print(main())