Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

2 ≦ N ≦ 2*10^5

1 ≦ K, L≦ 10^5

1 ≦ p_i, q_i, r_i, s_i ≦ N

p_i < q_i

r_i < s_i

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

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

Input

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

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

Output

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

Sample Input 1

4 3 1
1 2
2 3
3 4
2 3

Sample Output 1

1 2 2 1

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

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

Sample Input 2

4 2 2
1 2
2 3
1 4
2 3

Sample Output 2

1 2 2 1

Sample Input 3

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

Sample Output 3

1 1 2 1 2 2 2



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


Sample output:
1 2 2 1

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

import sys

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split(" ")

    while len(tokens) == 3:
        n, k, l = map(lambda x: int(x), tokens)

        roads = [[0] * n for i in xrange(n)]
        railways = [[0] * n for i in xrange(n)]

        for i in xrange(0, n):
            roads[i][i] = 1
            railways[i][i] = 1

        for i in xrange(0, k):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            roads[x - 1][y - 1] = 1
            roads[y - 1][x - 1] = 1

        for i in xrange(0, l):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            railways[x - 1][y - 1] = 1
            railways[y - 1][x - 1] = 1

        for t in xrange(0, n):
            for i in xrange(0, n):
                for j in xrange(0, n):
                    if roads[i][t] == 1 and roads[t][j] == 1:
                        roads[i][j] = 1
                    if railways[i][t] == 1 and railways[t][j] == 1:
                        railways[i][j] = 1

        results = []
        for i in xrange(0, n):
            count = 0
            for j in xrange(0, n):
                if roads[i][j] == 1 and railways[i][j] == 1:
                    count += 1
            results.append(str(count))
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split(" ")
if __name__ == "__main__":
    main(sys.argv)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

class DFS:
    def __init__(self, adjacent):
        self.adjacent = adjacent
        self.table = [0] * len(adjacent)
        self.group = 0
        for i in range(len(adjacent)):
            if self.table[i] == 0:
                self.group += 1
                self.dfs(i)

    def dfs(self, node):
        if self.table[node] == 0:
            self.table[node] = self.group
            for x in self.adjacent[node]:
                self.dfs(x)

    def find(self, x): return self.table[x]
    def getTableSet(self): return self.table

if __name__ == '__main__':
    sys.setrecursionlimit(100000)

    n, k, l = map(int, input().split())
    loadlist = [[] for _ in range(n)]
    trainlist = [[] for _ in range(n)]
    for _ in range(k):
        p, q = map(lambda x: int(x) - 1, input().split())
        loadlist[p].append(q)
        loadlist[q].append(p)
    for _ in range(l):
        r, s = map(lambda x: int(x) - 1, input().split())
        trainlist[r].append(s)
        trainlist[s].append(r)

    s = DFS(loadlist)
    loadresult = {-1: []}
    loadresultDic = defaultdict(lambda: -1)
    for i in range(n):
        result = s.find(i)
        if result in loadresult:
            loadresult[result].append(i)
        else:
            loadresult[result] = [i]
        loadresultDic[i] = result

    s = DFS(trainlist)
    trainresult = {-1: []}
    trainresultDic = defaultdict(lambda: -1)
    for i in range(n):
        result = s.find(i)
        if result in trainresult:
            trainresult[result].append(i)
        else:
            trainresult[result] = [i]
        trainresultDic[i] = result

    print(" ".join([str(len(set(loadresult[loadresultDic[i]]) & \
                    set(trainresult[trainresultDic[i]]))) for i in range(n)]))

Submission status: Time Limit Exceeded

Solution code:
a, b, c = map(int, raw_input().split())

x = []
t = [1 for a in range(a + 1)]

for _ in range(b):
	z = map(int, raw_input().split())
	l = []
	x.append(z)
	for tt in x:
		if z[0] == tt[0] and [z[1], tt[1]] not in x:
			l.append([z[1],tt[1]])
		if z[1] == tt[1] and [z[0],tt[0]] not in x:
			l.append([z[0],tt[0]])
		if z[0] == tt[1] and [z[1],tt[0]] not in x:
			l.append([z[1],tt[0]])
		if z[1] == tt[0] and [z[0],tt[1]] not in x:
			l.append([z[0],tt[1]])
	x = x + l
	xq = []
	for tt in x:
		if tt not in xq:
			xq.append(tt)
	x = xq

for _ in range(c):
	z = map(int, raw_input().split())
	if z in x:
		t[z[0]] += 1
		t[z[1]] += 1
	elif [z[1], z[0]] in x:
		t[z[0]] += 1
		t[z[1]] += 1
# print x
for i in range(1, a + 1):
	print t[i],

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

class DFS:
    def __init__(self, adjacent):
        self.adjacent = adjacent
        self.table = [0] * len(adjacent)
        self.group = 0
        for i in range(len(adjacent)):
            if self.table[i] == 0:
                self.group += 1
                self.dfs(i)

    def dfs(self, node):
        if self.table[node] == 0:
            self.table[node] = self.group
            for x in self.adjacent[node]:
                self.dfs(x)

    def find(self, x): return self.table[x]
    def getTableSet(self): return self.table

if __name__ == '__main__':
    n, k, l = map(int, input().split())
    loadlist = [[] for _ in range(n)]
    trainlist = [[] for _ in range(n)]
    for _ in range(k):
        p, q = map(lambda x: int(x) - 1, input().split())
        loadlist[p].append(q)
        loadlist[q].append(p)
    for _ in range(l):
        r, s = map(lambda x: int(x) - 1, input().split())
        trainlist[r].append(s)
        trainlist[s].append(r)

    s = DFS(loadlist)
    loadresult = {-1: []}
    loadresultDic = defaultdict(lambda: -1)
    for i in range(n):
        result = s.find(i)
        if result in loadresult:
            loadresult[result].append(i)
        else:
            loadresult[result] = [i]
        loadresultDic[i] = result

    s = DFS(trainlist)
    trainresult = {-1: []}
    trainresultDic = defaultdict(lambda: -1)
    for i in range(n):
        result = s.find(i)
        if result in trainresult:
            trainresult[result].append(i)
        else:
            trainresult[result] = [i]
        trainresultDic[i] = result

    print(" ".join([str(len(set(loadresult[loadresultDic[i]]) & \
                    set(trainresult[trainresultDic[i]]))) for i in range(n)]))

Submission status: Time Limit Exceeded

Solution code:
#http://www.geocities.jp/m_hiroi/light/pyalgo61.html
class UF(object):
    def __init__(self, n):
        self.table = [None for i in range(n)]
    def find(self, x):
        if self.table[x] is None:
            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:
            self.table[s2] = s1

n, k, l = [int(x) for x in raw_input().split()]
d = UF(n)
t = UF(n)
for i in range(k):
    p, q = [int(x) - 1 for x in raw_input().split()]
    d.union(p, q)
for i in range(l):
    r, s = [int(x) - 1 for x in raw_input().split()]
    t.union(r, s)
d2 = [[] for i in range(n)]
t2 = [[] for i in range(n)]
for i in range(n):
    d2[d.find(i)].append(i)
    t2[t.find(i)].append(i)
for i in range(n):
    print len(set(d2[d.find(i)]).intersection(t2[t.find(i)])),

Submission status: Time Limit Exceeded

Solution code:
a, b, c = map(int, raw_input().split())

x = []
t = [1 for a in range(a + 1)]

for _ in range(b):
	z = map(int, raw_input().split())
	l = []
	x.append(z)
	for tt in x:
		if z[0] == tt[0] and [z[1],tt[1]] not in x:
			l.append([z[1],tt[1]])
		if z[1] == tt[1] and [z[0],tt[0]] not in x:
			l.append([z[0],tt[0]])
		if z[0] == tt[1] and [z[1],tt[0]] not in x:
			l.append([z[1],tt[0]])
		if z[1] == tt[0] and [z[0],tt[1]] not in x:
			l.append([z[0],tt[1]])
	x = x + l

for _ in range(c):
	z = map(int, raw_input().split())
	if z in x:
		t[z[0]] += 1
		t[z[1]] += 1
	elif [z[1], z[0]] in x:
		t[z[0]] += 1
		t[z[1]] += 1

for i in range(1, a + 1):
	print t[i],

Submission status: Time Limit Exceeded

Solution code:
n, k, l = [int(x) for x in raw_input().split()]
d = [None for i in range(n)]
t = [None for i in range(n)]
for i in range(k):
    p, q = [int(x) - 1 for x in raw_input().split()]
    j = p
    while True:
        if d[j] is None:
            break
        j = d[j]
    j2 = q
    while True:
        if d[j2] is None:
            break
        j2 = d[j2]
    if j == j2:
        continue
    d[j2] = j
for i in range(l):
    r, s = [int(x) - 1 for x in raw_input().split()]
    j = r
    while True:
        if t[j] is None:
            break
        j = t[j]
    j2 = s
    while True:
        if t[j2] is None:
            break
        j2 = t[j2]
    if j == j2:
        continue
    t[j2] = j
d2 = dict((i, []) for i, v in enumerate(d) if v is None)
t2 = dict((i, []) for i, v in enumerate(t) if v is None)
for i, v in enumerate(d):
    if v is None:
        v2 = i
    else:
        v2 = v
        while True:
            if d[v2] is None:
                break
            v2 = d[v2]
        d[i] = v2
    d2[v2].append(i)
for i, v in enumerate(t):
    if v is None:
        v2 = i
    else:
        v2 = v
        while True:
            if t[v2] is None:
                break
            v2 = t[v2]
        t[i] = v2
    t2[v2].append(i)
for i in range(n):
    jd = d[i]
    if jd is None:
        jd = i
    jt = t[i]
    if jt is None:
        jt = i
    d2[jd]
    t2[jt]
    print len(set(d2[jd]).intersection(t2[jt])),

Submission status: Time Limit Exceeded

Solution code:
a, b, c = map(int, raw_input().split())

x = []
t = [1 for a in range(a + 1)]

for _ in range(b):
	z = map(int, raw_input().split())
	l = []
	x.append(z)
	for tt in x:
		if z[0] == tt[0]:
			l.append([z[1],tt[1]])
		if z[1] == tt[1]:
			l.append([z[0],tt[0]])
		if z[0] == tt[1]:
			l.append([z[1],tt[0]])
		if z[1] == tt[0]:
			l.append([z[0],tt[1]])
	x = x + l

for _ in range(c):
	z = map(int, raw_input().split())
	if z in x:
		t[z[0]] += 1
		t[z[1]] += 1
	elif [z[1], z[0]] in x:
		t[z[0]] += 1
		t[z[1]] += 1

for i in range(1, a + 1):
	print t[i],

Submission status: Memory Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k,l = list(map(int, input().split()))
from collections import defaultdict
ns0 = defaultdict(list)
ns1 = defaultdict(list)
for i in range(k):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns0[p].append(q)
    ns0[q].append(p)
for i in range(l):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns1[p].append(q)
    ns1[q].append(p)
def sub(ns):
    seen = [None]*n
    num = 1
    for i in range(n):
        if seen[i] is not None:
            continue
        q = [i]
        seen[i] = num
        while q:
            u = q.pop()
            for v in ns[u]:
                if seen[v] is not None:
                    continue
                seen[v] = num
                q.append(v)
        num += 1
    return seen

s1 = sub(ns0)
s2 = sub(ns1)

import gc
del ns0, ns1
gc.collect()

d1 = [None]*(max(s1)+1)
d2 = [None]*(max(s2)+1)
def update(d,ind,i):
    if d[ind] is None:
        d[ind] = set([i])
    else:
        d[ind].add(i)
for i in range(n):
    update(d1,s1[i],i)
    update(d2,s2[i],i)
#     d1[s1[i]].add(i)
#     d2[s2[i]].add(i)
d = {}
ans = [None]*n
for i in range(n):
    u,v = s1[i], s2[i]
    if (u,v) not in d:
        d[u,v] = len(d1[u] & d2[v])
    ans[i] = d[u,v]
write(" ".join(map(str, ans)))

Submission status: Memory Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k,l = list(map(int, input().split()))
from collections import defaultdict
ns0 = defaultdict(list)
ns1 = defaultdict(list)
for i in range(k):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns0[p].append(q)
    ns0[q].append(p)
for i in range(l):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns1[p].append(q)
    ns1[q].append(p)
def sub(ns):
    seen = [None]*n
    num = 1
    for i in range(n):
        if seen[i] is not None:
            continue
        q = [i]
        seen[i] = num
        while q:
            u = q.pop()
            for v in ns[u]:
                if seen[v] is not None:
                    continue
                seen[v] = num
                q.append(v)
        num += 1
    return seen

s1 = sub(ns0)
s2 = sub(ns1)

import gc
del ns0, ns1
gc.collect()

d1 = defaultdict(set)
d2 = defaultdict(set)
for i in range(n):
    d1[s1[i]].add(i)
    d2[s2[i]].add(i)
d = {}
ans = [None]*n
for i in range(n):
    u,v = s1[i], s2[i]
    if (u,v) not in d:
        d[u,v] = len(d1[u] & d2[v])
    ans[i] = d[u,v]
write(" ".join(map(str, ans)))

Submission status: Memory Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k,l = list(map(int, input().split()))
from collections import defaultdict
ns0 = defaultdict(set)
ns1 = defaultdict(set)
for i in range(k):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns0[p].add(q)
    ns0[q].add(p)
for i in range(l):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns1[p].add(q)
    ns1[q].add(p)
def sub(ns):
    seen = [None]*n
    num = 1
    for i in range(n):
        if seen[i] is not None:
            continue
        q = [i]
        seen[i] = num
        while q:
            u = q.pop()
            for v in ns[u]:
                if seen[v] is not None:
                    continue
                seen[v] = num
                q.append(v)
        num += 1
    return seen

s1 = sub(ns0)
s2 = sub(ns1)

import gc
del ns0, ns1
gc.collect()

d1 = defaultdict(set)
d2 = defaultdict(set)
for i in range(n):
    d1[s1[i]].add(i)
    d2[s2[i]].add(i)
d = {}
ans = [None]*n
for i in range(n):
    u,v = s1[i], s2[i]
    if (u,v) not in d:
        d[u,v] = len(d1[u] & d2[v])
    ans[i] = d[u,v]
write(" ".join(map(str, ans)))

Submission status: Memory Limit Exceeded

Solution code:
from collections import Counter
from collections import deque

def bfs(graph):
    root = [i for i in range(N)]
    visited = [False] * N
    
    for i in range(N):
        if not visited[i]:
            q = graph[i]
            visited[i] = True
            
            while q:
                v = q.pop()
                root[v] = i
                visited[v] = True
                for u in graph[v]:
                    if not visited[u]:
                        visited[u] = True
                        q.append(u)
                        root[u] = i
                        
    return root

N, K, L = map(int, input().split())
load = [deque() for i in range(N)]
train = [deque() for i in range(N)]

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

load_root = bfs(load)
train_root = bfs(train)

count = Counter()

city = [(i, j) for i, j in zip(load_root, train_root)]

for c in city:
    count[c] += 1
    
for c in city:
    print(count[c], '', end='')

Submission status: Memory Limit Exceeded

Solution code:
#!/usr/bin/python

import sets
import sys

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split(" ")

    while len(tokens) == 3:
        n, k, l = map(lambda x: int(x), tokens)

        roads = [set([i]) for i in xrange(n)]
        railways = [set([i]) for i in xrange(n)]

        for i in xrange(0, k):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            roads[x - 1].add(y - 1)

        for i in xrange(0, l):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            railways[x - 1].add(y - 1)

        for i in xrange(0, n):
            for j in roads[i]:
                if i != j:
                    roads[j].update(roads[i])

            for j in railways[i]:
                if i != j:
                    railways[j].update(railways[i])

        results = []
        for i in xrange(0, n):
            results.append(str(len(roads[i].intersection(railways[i]))))
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split(" ")
if __name__ == "__main__":
    main(sys.argv)

Submission status: Accepted

Solution code:
from collections import Counter


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

def root(x):
    while p[x] >= 0:
        x = p[x]
    return x

def unite(x, y):
    x, y = root(x), root(y)
    if x == y:
        return
    if x > y:
        x, y = y, x
    p[x] += p[y]
    p[y] = x

def g(x):
    global p
    p = [-1]*n
    for _ in range(x):
        a, b = map(int, input().split())
        unite(a-1, b-1)
    return [root(i) for i in range(n)]

z = [*zip(g(k), g(l))]
count = Counter(z)
print(*[count[t] for t in z])

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,K,L=map(int,input().split())
sys.setrecursionlimit(300000)
class uf:
    def __init__(self,n):
        self.n=n
        self.l=[-1]*n
    def ro(self,n):         #root
        if self.l[n]<0:
            return n
        r=self.ro(self.l[n])
        self.l[n]=r
        return r
    def me(self,a,b):       #merge
        ra=self.ro(a-1)
        rb=self.ro(b-1)
        if self.l[ra]>self.l[rb]:
            ra,rb=rb,ra
        if ra!=rb:
            self.l[ra]+=self.l[rb]
            self.l[rb]=ra
    def size(self,n):
        return -self.l[self.ro(n)]
    def sa(self,a,b):       #same
        return self.ro(a)==self.ro(b)
    def rl(self):           #roots list
        return [i for i,v in enumerate(self.l) if v<0]
    
    def len(self):          #len(roots)
        return len(self.rl())
    def ul(self):
        d={n:i for i,n in enumerate(self.rl())}
        m=[[]for i in range(self.len())]
        for i in range(self.n):
            m[d[self.ro(i)]].append(i)
        return m
    def __str__(self):
        return f"{self.ul()}"
    def __setitem__(self,i,v):
        self.l[i]=v
up=uf(N)
for i in range(K):
    up.me(*map(int,input().split()))
ur=uf(N)
for i in range(L):
    ur.me(*map(int,input().split()))
l=[0]*N
from collections import defaultdict
for i in up.ul():
    d = defaultdict(int)
    for j in i:
        d[ur.ro(j)]+=1
    for j in i:
        l[j]=d[ur.ro(j)]
print(*l)

Submission status: Accepted

Solution code:
from collections import Counter


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

def root(x):
    while p[x] >= 0:
        x = p[x]
    return x

def unite(x, y):
    x, y = root(x), root(y)
    if x == y:
        return
    if x > y:
        x, y = y, x
    p[x] += p[y]
    p[y] = x

def g(x):
    global p
    p = [-1]*n
    for _ in range(x):
        a, b = map(int, input().split())
        unite(a-1, b-1)
    return [root(i) for i in range(n)]

z = [*zip(g(k), g(l))]
count = Counter(z)
print(*[count[t] for t in z])

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right


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

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


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.union(p-1, q-1)

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

uf_pair = sorted([(uf1.find(i), uf2.find(i)) for i in range(N)])

ans = []
for i in range(N):
    key = (uf1.find(i), uf2.find(i))
    ans.append(bisect_right(uf_pair, key) - bisect_left(uf_pair, key))

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

Submission status: Accepted

Solution code:
from collections import Counter
N, K, L = map(int, input().split())
# Union-Find
def get_root(par, node):
  if par[node] == node:
    return node
  root = get_root(par, par[node])
  par[node] = root
  return root

def union(par, rank, a, b):
  root_a, root_b = get_root(par, a), get_root(par, b)
  if root_a == root_b:
    return
  rank_a, rank_b = rank[root_a], rank[root_b]
  if rank_a < rank_b:
    par[root_a] = root_b
  else:
    par[root_b] = root_a
    if rank_a == rank_b:
      rank[root_a] += 1

par1 = [i for i in range(N)]
rank1 = [1] * N
for _ in range(K):
    a, b = map(int, input().split())
    union(par1, rank1, a-1, b-1)

par2 = [i for i in range(N)]
rank2 = [1] * N
for _ in range(L):
    a, b = map(int, input().split())
    union(par2, rank2, a-1, b-1)

ct = Counter()
for i in range(N):
    a = get_root(par1, i)
    b = get_root(par2, i)
    ct[(a, b)] += 1

print(' '.join([str(ct[(par1[i], par2[i])]) for i in range(N)]))

Submission status: Accepted

Solution code:
from collections import Counter

class Unionfind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)
        
    def find(self, x):
        if(self.parents[x] < 0):
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
        
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if(x == y):
            return
        
        if(self.parents[x] > self.parents[y]):
            x, y = y, x
            
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}:{}'.format(r, self.members(r)) for r in self.roots())

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

uf = Unionfind(N)
uf1 = Unionfind(N)

for _ in range(K):
    p, q = map(int, input().split())
    uf.union(p-1, q-1)
    
for _ in range(L):
    r, s = map(int, input().split())
    uf1.union(r-1, s-1)
    
pairs = [(uf.find(i), uf1.find(i)) for i in range(N)]
#print(pairs)
    
c = Counter(pairs)
#print(c)
ans = [c[pairs[i]] for i in range(N)]

print(*ans)

Submission status: Accepted

Solution code:
n,k,l=map(int,input().split())
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        news=[]
        p=self._parents
        y=p[x]
        while y>=0:
            news.append(x);x,y=y,p[y]
        if len(news)!=1:
            for P in news:p[P]=x
        return x

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
road=UnionFind(1,n)
rail=UnionFind(1,n)

for i in range(k):
    road.unite(*map(int,input().split()))
for i in range(l):
    rail.unite(*map(int,input().split()))
from collections import defaultdict
d=defaultdict(int)

for i in range(1,n+1):
    ap,op=rail.find(i),road.find(i)
    d[ap*(n+1)+op]+=1
print(*[d[road.find(i)+rail.find(i)*(n+1)]for i in range(1,n+1)])

Submission status: Accepted

Solution code:
import sys

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


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

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

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

pair_list = []
for i in range(N):
    pair_list.append((uf_road.find(i), uf_train.find(i), i))

pair_list.sort()
ans = [0] * N

pair = (pair_list[0][0], pair_list[0][1])
countup_list = [pair_list[0][2]]
for i in range(1,N):
    if pair == (pair_list[i][0], pair_list[i][1]):
        countup_list.append(pair_list[i][2])
    else:
        for c in countup_list:
            ans[c] += len(countup_list)
        pair = (pair_list[i][0], pair_list[i][1])
        countup_list = [pair_list[i][2]]

for c in countup_list:
    ans[c] += len(countup_list)
    
for i in range(N):
    print(ans[i], end=" ")

Submission status: Accepted

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

par = [i for i in range(N)]

def find(x, P):
    if P[x] == x:
        return x
    else:
        b = find(P[x], P)
        P[x] = b
        return b

def unite(x, y, P):
    root_x = find(x, P)
    root_y = find(y, P)
    if root_y > root_x:
        P[root_x] = root_y
    else:
        P[root_y] = root_x

par2 = [i for i in range(N)]

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

for _ in range(L):
    p, q = map(int, input().split())
    unite(p-1, q-1, par2)
#print(par2)

r=[]
for i in range(N):
    r.append((find(i,par), find(i, par2)))

import collections
count = collections.Counter(r)
#print(count)

for i in range(N):
  ans = count[r[i]]
  if i == N-1:
    print(ans)
  else:
    print(ans, end=' ')

Submission status: Accepted

Solution code:
from collections import Counter

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

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

def union(c,x,y):
  rx=root(c,x)
  ry=root(c,y)
  if rx>ry:
    c[rx]=ry
  else:
    c[ry]=rx

for i in range(k):
  a,b=map(int,input().split())
  union(city1,a-1,b-1)
for i in range(l):
  a,b=map(int,input().split())
  union(city2,a-1,b-1)
r=[]
for i in range(n):
  r.append((root(city1,i),root(city2,i)))
c=Counter(r)
for i in range(n):
  ans=c[r[i]]
  if i==n-1:
    print(ans)
  else:
    print(ans,end=' ')

Submission status: Accepted

Solution code:
from collections import Counter

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

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

def union(c,x,y):
  rx=root(c,x)
  ry=root(c,y)
  if rx>ry:
    c[rx]=ry
  else:
    c[ry]=rx

for i in range(k):
  a,b=map(int,input().split())
  union(city1,a-1,b-1)
for i in range(l):
  a,b=map(int,input().split())
  union(city2,a-1,b-1)
r=[]
for i in range(n):
  r.append((root(city1,i),root(city2,i)))
c=Counter(r)
for i in range(n):
  ans=c[r[i]]
  if i==n-1:
    print(ans)
  else:
    print(ans,end=' ')

Submission status: Accepted

Solution code:
# unionfind
class Uf:
	def __init__(self, N):
		self.p = list(range(N))
		self.rank = [0] * N
		self.size = [1] * N
	#検索 ノード番号を受け取って一番上の親ノードの番号を帰す
	def root(self, x):
		if self.p[x] != x:
			self.p[x] = self.root(self.p[x])

		return self.p[x]
	#同じ集合に属するか判定
	def same(self, x, y):
		return self.root(x) == self.root(y)
	#併合
	def unite(self, x, y):
		# 根を探す
		u = self.root(x)
		v = self.root(y)

		if u == v: return

		#木の高さを比較し、低いほうから高いほうに辺を張る
		if self.rank[u] < self.rank[v]:
			self.p[u] = v
			self.size[v] += self.size[u]
			self.size[u] = 0
		else:
			self.p[v] = u
			self.size[u] += self.size[v]
			self.size[v] = 0
			#木の高さが同じなら片方を1増やす
			if self.rank[u] == self.rank[v]:
				self.rank[u] += 1
	#ノード番号を受け取って、そのノードが含まれている集合のサイズを返す
	def count(self, x):
		return self.size[self.root(x)]

from collections import Counter	
N, K, L = map(int, input().split())
uf_load = Uf(N)
uf_rail = Uf(N)

for i in range(K):
	p, q = map(int, input().split())
	p-=1
	q-=1
	uf_load.unite(p, q)
for _ in range(L):
	r, s = map(int, input().split())
	r-=1
	s-=1
	uf_rail.unite(r, s)

union_sets = [(uf_load.root(i), uf_rail.root(i)) for i in range(N)]
counts=Counter(union_sets)
ans = [counts[union_set] for union_set in union_sets]
print(*ans)