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:
from collections import defaultdict

class Unionfind:

    __slots__ = ['parents','sizes']

    def __init__(self, n):
        self.parents = list(range(n))
        self.sizes = [1]*n

    def root(self, x):
        if self.parents[x] == x:
            return x
        else:
            root_x = self.root(self.parents[x])
            self.parents[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.sizes[x] += self.sizes[y]
        self.parents[y] = x

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

    # 集合自体の数 ({1,2}, {3}, {4} : kind -> 3)
    def kind(self):
        for v in range(N):
            self.root(v)
        return len(list(set(self.parents)))

    # xが属する集合の要素の数　({1,2,3} : size(2) -> 3)
    def size(self, x):
        self.sizes[x] = self.sizes[self.root(x)]
        return self.sizes[x]

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

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

for _ in range(L):
    r, s = map(int,input().split())
    r -= 1; s -= 1
    train.unite(r, s)

ans_list = []

r = defaultdict(set)
for i in range(N):
    r[road.root(i)].add(i)

t = defaultdict(set)
for i in range(N):
    t[train.root(i)].add(i)

ans_list = []

for i in range(N):
    ans = len(r[road.root(i)] & t[train.root(i)])
    ans_list.append(ans)

print(*ans_list)

Submission status: Time Limit Exceeded

Solution code:
class Unionfind:

    __slots__ = ['parents','sizes']

    def __init__(self, n):
        self.parents = list(range(n))
        self.sizes = [1]*n

    def root(self, x):
        if self.parents[x] == x:
            return x
        else:
            root_x = self.root(self.parents[x])
            self.parents[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.sizes[x] += self.sizes[y]
        self.parents[y] = x

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

    # 集合自体の数 ({1,2}, {3}, {4} : kind -> 3)
    def kind(self):
        for v in range(N):
            self.root(v)
        return len(list(set(self.parents)))

    # xが属する集合の要素の数　({1,2,3} : size(2) -> 3)
    def size(self, x):
        self.sizes[x] = self.sizes[self.root(x)]
        return self.sizes[x]

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

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

for _ in range(L):
    r, s = map(int,input().split())
    r -= 1; s -= 1
    train.unite(r, s)

ans_list = []

r = dict()
for i in range(N):
    r[i] = set()
for i in range(N):
    r[road.root(i)].add(i)

t = dict()
for i in range(N):
    t[i] = set()
for i in range(N):
    t[train.root(i)].add(i)

ans_list = []

for i in range(N):
    ans = len(r[road.root(i)] & t[train.root(i)])
    ans_list.append(ans)

print(*ans_list)

Submission status: Time Limit Exceeded

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

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 main():
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    train = UnionFind(N)
    for _ in range(K):
        p, q = map(int, input().split())
        p -= 1
        q -= 1
        road.union(p,q)
    for _ in range(L):
        r, s = map(int, input().split())
        r -= 1
        s -= 1
        train.union(r,s)

    ans = [0] * N
    for i in range(N):
        a = set(road.members(i))
        b = set(train.members(i))
        ans[i] = len(list(a & b))

    print(*ans)




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def getlist():
	return list(map(int, input().split()))

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

    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 main():
	#受け取り、処理
	N, K, L = getlist()
	UFp = UnionFind(N)
	UFr = UnionFind(N)
	for i in range(K):
		p, q = getlist()
		UFp.union(p, q)
	for i in range(L):
		r, s = getlist()
		UFr.union(r, s)

	s1 = UFp.par
	s2 = UFr.par
	s3 = []
	for i in range(1, N + 1):
		s3.append(sorted([s1[i], s2[i]]))

	X = [[0] * (N + 1) for i in range(N + 1)]
	for i in range(N):
		X[s3[i][0]][s3[i][1]] += 1

	ans = []
	for i in range(N):
		ans.append(str(X[s3[i][0]][s3[i][1]]))

	print(" ".join(ans))


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def getlist():
	return list(map(int, input().split()))

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.size = [1] * (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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            if self.same_check(x, y) != True:
                self.size[y] += self.size[x]
                self.size[x] = 0
            self.par[x] = y
        else:
            if self.same_check(x, y) != True:
               self.size[x] += self.size[y]
               self.size[y] = 0
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
               self.rank[x] += 1

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

#受け取り、処理
N, K, L = getlist()
UFp = UnionFind(N)
UFr = UnionFind(N)
for i in range(K):
	p, q = getlist()
	UFp.union(p, q)
for i in range(L):
	r, s = getlist()
	UFr.union(r, s)

s1 = UFp.par
s2 = UFr.par
s3 = []
for i in range(1, N + 1):
	s3.append(sorted([s1[i], s2[i]]))

X = [[0] * (N + 1) for i in range(N + 1)]
for i in range(N):
	X[s3[i][0]][s3[i][1]] += 1

ans = []
for i in range(N):
	ans.append(str(X[s3[i][0]][s3[i][1]]))

print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind :
    """
    Union Find木
    ---
    頂点のインデックスは0~

    Attributes
    ---
    parent : list<int>
        親のリスト．parent[頂点のインデックス] = 親のインデックス
    height : list<int>
        各木の高さ
    size : list<int>
        各木の頂点数
    component : int
        連結成分の数
    """

    def __init__(self, size) :
        """
        Parameters
        ---
        size : int
            頂点数
        """
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        """
        親のインデックスの取得

        Parameters
        ---
        index : int
            取得する頂点のインデックス

        Returns
        ---
        rootIndex : int
            指定した頂点の根のインデックス
        """
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        """
        木の結合

        Parameters
        ---
        index1 : int
        index2 : int
            結合する頂点のインデックス
        """
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        """
        同じ木に属するかを判定する

        Parameters
        ---
        index1 : int
        index2 : int

        Returns
        ---
        boolean
        """
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        """
        指定した頂点の属する木の大きさを取得する
        """
        return self.size[self.root(index)]

    def getComponent(self) :
        """
        連結成分数を取得する
        """
        return self.component

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

train = UnionFind(N)
road = UnionFind(N)

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

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

trainComp = defaultdict(set)
roadComp = defaultdict(set)
for i in range(N):
    trainComp[train.root(i)].add(i)
    roadComp[road.root(i)].add(i)

ans = [len(trainComp[train.root(i)] & roadComp[road.root(i)]) for i in range(N)]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
#
# class UnionFind():
#     def __init__(self,n):
#         self.par = [i for i in range(n+1)]
#         self.rank = [0 for _ in range(n+ 1)]
#     def find(self,x):
#         if self.par[x] == x:
#             return x
#         self.par[x] = self.find(self.par[x])
#         return  self.par[x]
#
#     def same_check(self,a,b):
#             return self.find(a) == self.find(b)
#
#     def union(self,x,y):
#         if self.rank[x] > self.rank[y]:
#             self.par[y] = self.par[x]
#         else:
#             self.par[x] = self.par[y]
#             if self.rank[x] == self.rank[y]:
#                 self.rank[x] += 1

class UnionFind:
    def __init__(self, size):
        self.parent = [-1] * (size + 1)  # 非負なら親ノード，負ならグループの要素数

    def root(self, x):  # root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        elif self.parent[self.parent[x]] < 0:
            return self.parent[x]
        else:
            self.parent[x] = self.root(self.parent[x])  # xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y):  # merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]:  # xの要素数がyの要素数より「小さい」とき入れ替える
            x, y = y, x
        self.parent[x] += self.parent[y]  # xの要素数を更新
        self.parent[y] = x  # yをxにつなぐ
        return True

    def issame(self, x, y):  # same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)

    def size(self, x):  # size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]


def do():
    sys.setrecursionlimit(100000000)

    N,K,L = list(map(int, input().split(" ")))
    querys1 = [list(map(int, input().split(" "))) for i in range(K)]
    querys2 = [list(map(int, input().split(" "))) for i in range(L)]
    uf1 = UnionFind(N + 1)
    uf2 = UnionFind(N + 1)
    for query in querys1:
        a,b= query
        uf1.merge(a,b)
    for query in querys2:
        a, b = query
        uf2.merge(a, b)
    anss = []
    for i in range(N+1):
        cot = 0 #iを固定
        for j in range(N+1):
             if uf1.issame(i,j) and uf2.issame(i,j):
                cot += 1
        anss.append(str(cot))
    print( " ".join(anss[1:]))

if __name__ == "__main__":
    do()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)
    
    # 根を検索する関数
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])
  
    # 結合(unite)する関数
    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
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            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 get_depth(self, x):
        return self.rank[self.find(x)]
    
    # 要素が属する木のサイズを返す関数
    def get_size(self, x):
        return self.size[self.find(x)]
    
    # グループ数を返す関数
    def group_sum(self):
        c = 0
        for i in range(len(self.par)):
            if self.find(i) == i:
                c += 1
        return c

if __name__ == "__main__":
    N,K,L = map(int, input().split())
    uf_r = UnionFind(N)
    uf_t = UnionFind(N)

    for i in range(K):
        p, q = [int(i) for i in input().split()]
        uf_r.unite(p, q)
    
    for i in range(L):
        r, s = [int(i) for i in input().split()]
        uf_t.unite(r, s)
    
    pair = []
    for i in range(1,N+1):
        pair.append((uf_r.find(i), uf_t.find(i)))
    
    print(*[pair.count(pair[i]) for i in range(N)])

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)
    
    # 根を検索する関数
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])
  
    # 結合(unite)する関数
    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
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            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 get_depth(self, x):
        return self.rank[self.find(x)]
    
    # 要素が属する木のサイズを返す関数
    def get_size(self, x):
        return self.size[self.find(x)]
    
    # グループ数を返す関数
    def group_sum(self):
        c = 0
        for i in range(len(self.par)):
            if self.find(i) == i:
                c += 1
        return c

if __name__ == "__main__":
    N,K,L = map(int, input().split())
    uf_r = UnionFind(N)
    uf_t = UnionFind(N)

    for i in range(K):
        p, q = [int(i) for i in input().split()]
        uf_r.unite(p, q)
    
    for i in range(L):
        r, s = [int(i) for i in input().split()]
        uf_t.unite(r, s)
    
    pair = []
    for i in range(1,N+1):
        pair.append((uf_r.find(i), uf_t.find(i)))
    
    ans = []
    for i in range(N):
        ans.append(pair.count(pair[i]))
    
    print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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

def uft_root(g, a):
	if g[a] < 0:
		return a
	g[a] = uft_root(g, g[a])
	return g[a]

def uft_size(g, a):
	return -g[uft_root(g, a)]

def uft_merge(g, a, b):
	a, b = uft_root(g, a), uft_root(g, b)
	if a == b:
		return
	size_a, size_b = uft_size(g, a), uft_size(g, b)
	if size_a < size_b:
		a, b = b, a
		size_a, size_b = size_b, size_a
	g[a] -= size_b
	g[b] = a

g_pq = [[] for _ in range(N)]
for p, q in PQ:
	p, q = p - 1, q - 1
	g_pq[p] += [q]
	g_pq[q] += [p]

g_rs = [[] for _ in range(N)]
for r, s in RS:
	r, s = r - 1, s - 1
	g_rs[r] += [s]
	g_rs[s] += [r]

def dfs(v, g, uft, visited):
	if visited[v]:
		return
	visited[v] = True
	for n in g[v]:
		if visited[n]:
			continue
		uft_merge(uft, v, n)
		dfs(n, g, uft, visited)

visited_pq = [False] * N
visited_rs = [False] * N
uft_pq = [-1] * N
uft_rs = [-1] * N

for n in range(N):
	dfs(n, g_pq, uft_pq, visited_pq)
	dfs(n, g_rs, uft_rs, visited_rs)

group_pq, group_rs = {}, {}
for n in range(N):
	root_pq = uft_root(uft_pq, n)
	if not root_pq in group_pq:
		group_pq[root_pq] = {n}
	else:
		group_pq[root_pq] |= {n}
	root_rs = uft_root(uft_rs, n)
	if not root_rs in group_rs:
		group_rs[root_rs] = {n}
	else:
		group_rs[root_rs] |= {n}

for n in range(N):
	print(len(group_pq[uft_root(uft_pq, n)] & group_rs[uft_root(uft_rs, n)]), "", end="")
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

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()

road = [li_() for _ in range(k)]
rail = [li_() for _ in range(l)]

uf_road = UnionFind(n)
uf_rail = UnionFind(n)

for pi, qi in road:
    uf_road.unite(pi, qi)

for ri, si in rail:
    uf_rail.unite(ri, si)

for i in range(n):
    uf_road.find(i)
    uf_rail.find(i)

dic = defaultdict(int)

for road_par, rail_par in zip(uf_road.par, uf_rail.par):
    dic[(road_par, rail_par)] += 1

ans = []
for i in range(n):
    ans.append(dic[(uf_road.par[i], uf_rail.par[i])])

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

class UnionFind:
    def __init__(self, N):
        # negative value: represents the root of a tree; its absolute value is the size of the tree
        # positive value: the parent's index
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: # v is a root
            return v
        else:
            # path compression: reconnect v to the root
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) # the root of the tree including vertex u
        s2 = self.find(v) # the root of the tree including vertex v
        
        if s1 == s2: # u and v is in the same tree
            return False
        
        if self.rank[s1] > self.rank[s2]: # the tree including u is taller
            self.vertices[s1] += self.vertices[s2] # update the size of the bigger tree
            self.vertices[s2] = s1
        else: # the tree including v is taller
            self.vertices[s2] += self.vertices[s1] # update the size of the bigger tree
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]

N, K, L = map(int, input().split())
road = UnionFind(N)
rail = UnionFind(N)
for _ in range(K):
    p, q = map(int, input().split())
    road.union(p-1, q-1)
for _ in range(L):
    r, s = map(int, input().split())
    rail.union(r-1, s-1)
cnct_road = defaultdict(list)
cnct_rail = defaultdict(list)
for i in range(N):
    cnct_road[road.find(i)].append(i)
    cnct_rail[rail.find(i)].append(i)
ans = []
for i in range(N):
    ro = set(cnct_road[road.find(i)])
    ra = set(cnct_rail[rail.find(i)])
    ans.append(len(ro & ra))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class Union():
  def __init__(me,N):
    me.N = N
    me.up = [-1]*N
    me.down = [ [] for i in range(N) ]
  def union(me,a,b):
    ua = me.up[a] if me.up[a]!=-1 else a
    ub = me.up[b] if me.up[b]!=-1 else b
    if (ua == ub):
      return
    if ( len(me.down[ua]) < len(me.down[ub]) ):
      ub,ua = ua,ub
    for v in me.down[ub]:
      me.up[v] = ua
    me.down[ua].extend( me.down[ub] )
    me.down[ub] = []
    me.up[ub] = ua
    me.down[ua].append( ub )

N,K,L = [ int(it) for it in input().split() ]
uk = Union(N)
for a,b in [ [int(it)-1 for it in input().split()] for i in range(K) ]:
  uk.union(a,b)

ul = Union(N)
for a,b in [ [int(it)-1 for it in input().split()] for i in range(L) ]:
  ul.union(a,b)

for i in range(N):
  if ( uk.up[i] == -1 ):
    uk.down[i].append(i)
    uk.down[i] = set(uk.down[i])
  if ( ul.up[i] == -1 ):
    ul.down[i].append(i)
    ul.down[i] = set(ul.down[i])

li = [-1]*N
for i in range(N):
  if (li[i] != -1):
    continue
  ua = uk.up[i] if uk.up[i]!=-1 else i
  ub = ul.up[i] if ul.up[i]!=-1 else i
  uni = uk.down[ua] & ul.down[ub]
  for it in uni:
    li[i] = len(uni)

print ( " ".join( [ str(it) for it in li ]) )

Submission status: Time Limit Exceeded

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

RP=[i for i in range(N+1)]
Rsize=[1 for i in range(N+1)]
TP=[i for i in range(N+1)]
Tsize=[1 for i in range(N+1)]

def findR(a):
    if a==RP[a]:
        return a
    else:
        return findR(RP[a])
        
def findT(a):
    if a==TP[a]:
        return a
    else:
        return findT(TP[a])
        
def unionR(b,c):
    B=findR(b)
    C=findR(c)
    if Rsize[B]>=Rsize[c]:
        Rsize[B]+=Rsize[C]
        RP[C]=RP[B]
    else:
        Rsize[C]+=Rsize[B]
        RP[B]=RP[C]

def unionT(b,c):
    B=findT(b)
    C=findT(c)
    if Tsize[B]>=Tsize[c]:
        Tsize[B]+=Tsize[C]
        TP[C]=TP[B]
    else:
        Tsize[C]+=Tsize[B]
        TP[B]=TP[C]
        
for i in range(K):
    p,q=map(int,input().split())
    if findR(p)==findR(q):
        pass
    else:
        unionR(p,q)

for i in range(L):
    r,s=map(int,input().split())
    if findT(r)==findT(s):
        pass
    else:
        unionT(r,s)
        
L=collections.Counter()

for i in range(1,N+1):
    L[findR(i),findT(i)]+=1
#print(L)

ANS=L.items()
ANS=list(ANS)
ANS.sort()
K=[]
V=[]
for i in range(len(ANS)):
    K.append(ANS[i][0])
    V.append(ANS[i][1])
ans=str(V[bisect.bisect_left(K,(findR(1),findT(1)))])
for i in range(2,N+1):
    ans+=" "+str(V[bisect.bisect_left(K,(findR(i),findT(i)))])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

RP=[i for i in range(N+1)]
Rsize=[1 for i in range(N+1)]
TP=[i for i in range(N+1)]
Tsize=[1 for i in range(N+1)]

def findR(a):
    if a==RP[a]:
        return a
    else:
        return findR(RP[a])
        
def findT(a):
    if a==TP[a]:
        return a
    else:
        return findT(TP[a])
        
def unionR(b,c):
    B=findR(b)
    C=findR(c)
    if Rsize[B]>=Rsize[c]:
        Rsize[B]+=Rsize[C]
        RP[C]=RP[B]
    else:
        Rsize[C]+=Rsize[B]
        RP[B]=RP[C]

def unionT(b,c):
    B=findT(b)
    C=findT(c)
    if Tsize[B]>=Tsize[c]:
        Tsize[B]+=Tsize[C]
        TP[C]=TP[B]
    else:
        Tsize[C]+=Tsize[B]
        TP[B]=TP[C]
        
for i in range(K):
    p,q=map(int,input().split())
    if findR(p)==findR(q):
        pass
    else:
        unionR(p,q)

for i in range(L):
    r,s=map(int,input().split())
    if findT(r)==findT(s):
        pass
    else:
        unionT(r,s)
        
L=collections.defaultdict(int)
for i in range(1,N+1):
    L[findR(i),findT(i)]+=1

ans=str(L[findR(1),findT(1)])
for i in range(2,N+1):
    ans+=" "+str(L[findR(i),findT(i)])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
road = dd(list)
train = dd(list)
rd = dict()
td = dict()
ans = []
def gr(tree,start):
    island = set()
    rest = [start,]
    while rest:
        node = rest.pop()
        island.add(node)
        for x in tree[node]:
            if x not in island:
                rest.append(x)
    return(island)
n,k,l = map(int, input().split())
for _ in range(k):
    a,b = map(int, input().split())
    road[a].append(b)
    road[b].append(a)
for _ in range(l):
    a,b = map(int, input().split())
    train[a].append(b)
    train[b].append(a)
for i in range(1,n+1):
    if i not in rd:
      tempr = gr(road,i)
      for x in tempr:
        rd[x] = tempr
    if i not in td:
      tempt = gr(train,i)
      for x in tempt:
        td[x] = tempt
    ans.append(str(len(rd[i]&td[i])))
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
road = dd(list)
train = dd(list)
ans = []
def gr(tree,start):
    island = set()
    rest = [start,]
    while rest:
        node = rest.pop()
        island.add(node)
        for x in tree[node]:
            if x not in island:
                rest.append(x)
    return(island)
n,k,l = map(int, input().split())
for _ in range(k):
    a,b = map(int, input().split())
    road[a].append(b)
    road[b].append(a)
for _ in range(l):
    a,b = map(int, input().split())
    train[a].append(b)
    train[b].append(a)
for i in range(1,n+1):
    ans.append(str(len(gr(road,i)&gr(train,i))))
print(" ".join(ans))

Submission status: Time Limit Exceeded

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank 
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
#PQ = [ [int(j) for j in input().split()] for _ in range(K)]
#RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    p,q = map(int,input().split())
    UF1.unite(p,q)
for i in range(L):
    p,q = map(int,input().split())#RS[i]
    UF2.unite(p, q)
counter=[]
from collections import defaultdict
cntdic =defaultdict(int)
for i in range(1,N+1):
  counter.append(UF1.find(i)+UF2.find(i)*10**6)
  cntdic[counter[-1]]+=1 

ans = [0]*(N+1)
for i in range(1,N+1):
    ans[i] = cntdic[counter[i-1]]

del ans[0]
# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))

Submission status: Time Limit Exceeded

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank 
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
PQ = [ [int(j) for j in input().split()] for _ in range(K)]
RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    p,q = PQ[i]
    UF1.unite(p,q)
for i in range(L):
    p,q = RS[i]
    UF2.unite(p, q)
counter=[]
from collections import defaultdict
cntdic =defaultdict(int)
for i in range(1,N+1):
  counter.append(UF1.find(i)+UF2.find(i)*10**6)
  cntdic[counter[-1]]+=1 

ans = [0]*(N+1)
for i in range(1,N+1):
    ans[i] = cntdic[UF1.find(i)+UF2.find(i)*10**6]

del ans[0]
# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))