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:
import numpy as np

class UnionFindTree():
    # Union find tree
    # 2つの効率化　経路圧縮、ランク
    # つなげることはできるか分離することはできないので、木をつなげる方向に利用する
    # 
    def __init__(self, node_size):
        # node_num: 全体のノード数
        # parent: ノードがrootなら-1、親がいれば親の番号を入れる
        # size:
        # rank:  
        # self.parent =[-1] * node_size
        self.parent =[x for x in range(node_size)]
        
        self.size = [1] * node_size
        self.rank = [1] * node_size

        self.node_list = np.array([x for x in range(node_size)])
        self.member_dict = {}
    
    def find_root(self,node):
        # node属する木のrootを探す
        # たどった経路に含まれるnodeの親をrootにつなぎ替える
        if self.parent[node] == node:             # 自身がrootの場合
            root = node
        else:                                   # 自身がrootでない場合
            root = self.find_root(self.parent[node]) # 再帰的にrootを探す
            self.parent[node] = root            # たどった経路に含まれるnodeの親をrootにつなぎ替える(経路圧縮)
        return root

    def unite(self,node0, node1):
        # node0とnode1が含まれる木を結合する
        
        #node0 node1のrootを求める
        root_node0 = self.find_root(node0) 
        root_node1 = self.find_root(node1)

        if root_node0 != root_node1:
            # rankを比較しrankが小さい方の木を大きい方の木のrootにつなげる
            # rank is sameのときのみrankが増える

            # node1のグループをnode0のグループに結合
            if self.rank[root_node0] == self.rank[root_node1]: # rank is same
                self.parent[root_node1] = root_node0
                self.rank[root_node0] += 1
                self.size[root_node0] += self.size[root_node1]

            # node1のグループをnode0のグループに結合
            elif self.rank[root_node0] > self.rank[root_node1]:
                self.parent[root_node1] = root_node0
                self.size[root_node0] += self.size[root_node1]

            # node0のグループをnode1のグループに結合
            else:
                self.parent[root_node0] = root_node1
                self.size[root_node1] += self.size[root_node0]

    def same(self,node0,node1):
        #同じグループか確かめる
        return self.find_root(node0)==self.find_root(node1)

    def group_set(self,node):
        root_node = self.find_root(node)
        if root_node in self.member_dict:
            return self.member_dict[root_node]
        else:
            group_set = set(self.node_list[np.array(self.parent)==root_node])
            self.member_dict[root_node] = group_set
            return group_set


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

road_uft = UnionFindTree(N)
train_uft = UnionFindTree(N)

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

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

ans = ""
for i in range(N):
    road_group = road_uft.group_set(i)
    train_group = train_uft.group_set(i)
    ans += str(len(road_group&train_group)) + " "
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

class UnionFindTree():
    # Union find tree
    # 2つの効率化　経路圧縮、ランク
    # つなげることはできるか分離することはできないので、木をつなげる方向に利用する
    # 
    def __init__(self, node_size):
        # node_num: 全体のノード数
        # parent: ノードがrootなら-1、親がいれば親の番号を入れる
        # size:
        # rank:  
        # self.parent =[-1] * node_size
        self.parent =[x for x in range(node_size)]
        
        self.size = [1] * node_size
        self.rank = [1] * node_size

        self.node_list = np.array([x for x in range(node_size)])
    
    def find_root(self,node):
        # node属する木のrootを探す
        # たどった経路に含まれるnodeの親をrootにつなぎ替える
        if self.parent[node] == node:             # 自身がrootの場合
            root = node
        else:                                   # 自身がrootでない場合
            root = self.find_root(self.parent[node]) # 再帰的にrootを探す
            self.parent[node] = root            # たどった経路に含まれるnodeの親をrootにつなぎ替える(経路圧縮)
        return root

    def unite(self,node0, node1):
        # node0とnode1が含まれる木を結合する
        
        #node0 node1のrootを求める
        root_node0 = self.find_root(node0) 
        root_node1 = self.find_root(node1)

        if root_node0 != root_node1:
            # rankを比較しrankが小さい方の木を大きい方の木のrootにつなげる
            # rank is sameのときのみrankが増える

            # node1のグループをnode0のグループに結合
            if self.rank[root_node0] == self.rank[root_node1]: # rank is same
                self.parent[root_node1] = root_node0
                self.rank[root_node0] += 1
                self.size[root_node0] += self.size[root_node1]

            # node1のグループをnode0のグループに結合
            elif self.rank[root_node0] > self.rank[root_node1]:
                self.parent[root_node1] = root_node0
                self.size[root_node0] += self.size[root_node1]

            # node0のグループをnode1のグループに結合
            else:
                self.parent[root_node0] = root_node1
                self.size[root_node1] += self.size[root_node0]

    def same(self,node0,node1):
        #同じグループか確かめる
        return self.find_root(node0)==self.find_root(node1)

    def group_set(self,node):
        root_node = self.find_root(node)
        group_set = set(self.node_list[np.array(self.parent)==root_node])
        return group_set


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

road_uft = UnionFindTree(N)
train_uft = UnionFindTree(N)

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

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

ans = ""
for i in range(N):
    road_group = road_uft.group_set(i)
    train_group = train_uft.group_set(i)
    ans += str(len(road_group&train_group)) + " "
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K, L = map(int, input().split())
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 members(self, x):
        return -self.parents[self.find(x)]

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

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

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

for i in range(N):
    print(len(uf_k.members(i) & uf_l.members(i)))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N,K,L = map(int, input().split())
    class UnionFind():
        #n個の要素を番号0~n-1で管理する
        #parents:要素の親(1つ上), 要素が根の場合サイズを表す
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        #要素xの根を返す, その過程で経路圧縮も行う
        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
            #それぞれのsizeで比べる
            if self.parents[x] > self.parents[y]:
                x, y = y, x
            self.parents[x] += self.parents[y]
            self.parents[y] = x #根をくっつける(片方を親にする)

        #xが属するグループのsize
        def size(self, x):
            return -self.parents[self.find(x)]

        #xとyが同じグループかどうか
        def same(self, x, y):
            return self.find(x) == self.find(y)

        #xが属するグループの要素全てを返す
        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]
        
    douro = UnionFind(N+1)
    tetudou = UnionFind(N+1)
    for _ in range(K):
        p,q = map(int, input().split())
        douro.union(p,q)
    for _ in range(L):
        r,s = map(int, input().split())
        tetudou.union(r,s)
    res = [1]*N
    for i in range(1,N):
        for j in range(i+1, N+1):
            if douro.same(i, j) and tetudou.same(i, j):
                res[i-1] += 1
                res[j-1] += 1
    for i in range(N):
        if i <N-1:
            print(res[i], end=' ')
        else:
            print(res[i])



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N,K,L = map(int, input().split())
    class UnionFind():
        #n個の要素を番号0~n-1で管理する
        #parents:要素の親(1つ上), 要素が根の場合サイズを表す
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        #要素xの根を返す, その過程で経路圧縮も行う
        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
            #それぞれのsizeで比べる
            if self.parents[x] > self.parents[y]:
                x, y = y, x
            self.parents[x] += self.parents[y]
            self.parents[y] = x #根をくっつける(片方を親にする)

        #xが属するグループのsize
        def size(self, x):
            return -self.parents[self.find(x)]

        #xとyが同じグループかどうか
        def same(self, x, y):
            return self.find(x) == self.find(y)

        #xが属するグループの要素全てを返す
        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]
        
    douro = UnionFind(N+1)
    tetudou = UnionFind(N+1)
    for _ in range(K):
        p,q = map(int, input().split())
        douro.union(p,q)
    for _ in range(L):
        r,s = map(int, input().split())
        tetudou.union(r,s)
    for i in range(1,N+1):
        res = 0
        for j in range(1, N+1):
            if douro.same(i, j) and tetudou.same(i, j):
                res += 1
        if i <N:
            print(res, end=' ')
        else:
            print(res)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N,K,L = map(int, input().split())
    class UnionFind():
        #n個の要素を番号0~n-1で管理する
        #parents:要素の親(1つ上), 要素が根の場合サイズを表す
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        #要素xの根を返す, その過程で経路圧縮も行う
        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
            #それぞれのsizeで比べる
            if self.parents[x] > self.parents[y]:
                x, y = y, x
            self.parents[x] += self.parents[y]
            self.parents[y] = x #根をくっつける(片方を親にする)

        #xが属するグループのsize
        def size(self, x):
            return -self.parents[self.find(x)]

        #xとyが同じグループかどうか
        def same(self, x, y):
            return self.find(x) == self.find(y)

        #xが属するグループの要素全てを返す
        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]
        
    douro = UnionFind(N+1)
    tetudou = UnionFind(N+1)
    for _ in range(K):
        p,q = map(int, input().split())
        douro.union(p,q)
    for _ in range(L):
        r,s = map(int, input().split())
        tetudou.union(r,s)
    for i in range(1,N+1):
        res = 0
        for j in range(1, N+1):
            if douro.same(i, j) and tetudou.same(i, j):
                res += 1
        if i <N:
            print(res, end=' ')
        else:
            print(res)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N,K,L = map(int, input().split())
    class UnionFind():
        #n個の要素を番号0~n-1で管理する
        #parents:要素の親(1つ上), 要素が根の場合サイズを表す
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        #要素xの根を返す, その過程で経路圧縮も行う
        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
            #それぞれのsizeで比べる
            if self.parents[x] > self.parents[y]:
                x, y = y, x
            self.parents[x] += self.parents[y]
            self.parents[y] = x #根をくっつける(片方を親にする)

        #xが属するグループのsize
        def size(self, x):
            return -self.parents[self.find(x)]

        #xとyが同じグループかどうか
        def same(self, x, y):
            return self.find(x) == self.find(y)

        #xが属するグループの要素全てを返す
        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]
        
    douro = UnionFind(N+1)
    tetudou = UnionFind(N+1)
    for _ in range(K):
        p,q = map(int, input().split())
        douro.union(p,q)
    for _ in range(L):
        r,s = map(int, input().split())
        tetudou.union(r,s)
    for i in range(1,N+1):
        x = set(douro.members(i))
        y = set(tetudou.members(i))
        if i <N:
            print(len(x&y), end=' ')
        else:
            print(len(x&y))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n #各要素の親要素の番号を格納するリスト

    def find(self, x): #要素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が属するグループと要素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): #要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self,x,y): #要素x, yが同じグループに属するかどうかを返す
        return self.find(x)==self.find(y)

    def members(self,x): #要素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())

#print(list(uf.all_group_members().values())) #グループ一覧を表示

def main():
    n,k,l=map(int,input().split())
    ufr=UnionFind(n)
    uft=UnionFind(n)
    for i in range(k):
        x,y=map(int,input().split())
        ufr.union(x-1,y-1)
    for i in range(l):
        x,y=map(int,input().split())
        uft.union(x-1,y-1)
        
    for i in range(n):
        set_road=set(ufr.members(i))
        set_train=set(uft.members(i))
        print(len(set_road&set_train),end=" ")
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

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

#Union Find

#xの根を求める
def find(x,par):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x],par)
        return par[x]
#xとyの属する集合の併合
def unite(x,y,par):
    x = find(x,par)
    y = find(y,par)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y,par):
    return find(x,par) == find(y,par)

#xが属する集合の個数
def size(x,par):
    return -par[find(x,par)]

#xが属するグループの要素全てを返す
def members(x,par):
    root = find(x,par)
    return [i for i in range(n) if find(i,par) == root]

#全ての根の要素をlistで返す(一個下の関数で使う)
def roots(par):
    return [i for i,x in enumerate(par) if x < 0]

#グループ数を返す
def group_count(par):
    return len(roots(par))

#根をkey,そのグループに含まれる要素をvalueとして全てを辞書型で返す
def all_group_members(par):
    return {r: members(r,par) for r in roots(par)}

#初期化
#根なら-size,子なら親の頂点
par_a = [-1]*n
par_b = [-1]*n
"""
uniteでまとめ、findで見つける。
n(要素数)だけ最初に付け加えること。
"""

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

ans = [1]*n

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

for i in range(n-1):
    for j in range(i+1,n):
        if same(i,j,par_a) and same(i,j,par_b):
            ans[i]+=1
            ans[j]+=1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

class UnionFind:
    def __init__(self, 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 same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.parents[self.find(x)]

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())
        road.union(p, q)
    
    for _ in range(L):
        r, s = map(int, input().split())
        train.union(r, s)
    
    ans = [1] * (N + 1)
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            if road.same(i, j) and train.same(i, j):
                ans[i] += 1
                ans[j] += 1
    for i in ans[1:]:
        print(i)    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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())

ar = UnionFind(n)
br = UnionFind(n)
ans = [0]*n

#print(ar.parents)

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

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

for i in range(n):
    s = set(ar.members(i)) & set(br.members(i))
    ans[i] = len(s)
    print(len(s), end=" ")

Submission status: Time Limit Exceeded

Solution code:
n,k,l=map(int,input().split())
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]
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)
ans=[0]*n
for i in range(n):
  s1=set(uf1.members(i))
  s2=set(uf2.members(i))
  ans[i]=len(s1&s2)
print(*ans)

Submission status: Time Limit Exceeded

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


    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            if self.root(x)>self.root(y):
                self.roots[self.root(x)]=self.root(y)
            else:
                self.roots[self.root(y)]=self.root(x)
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train.unite(r-1,s-1)



count=defaultdict(lambda:0)
point=[]
for i in range(N):
    a=road.root(i)
    b=train.root(i)
    l=[a,b]
    point.append(l)
    count[str(l)]+=1
for i in point:
    print(count[str(i)],end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
class Unionfind:
    def __init__(self,n):
        self.n=n
        self.roots=[]
        self.dict=defaultdict(lambda:[])
        for i in range(self.n):
            self.roots.append(i)
            self.dict[i].append(i)

    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            if self.root(x)>self.root(y):
                #self.dict[self.root(y)]=self.dict[self.root(y)]+self.dict[self.root(x)]
                #self.dict[self.root(x)]=[]
                self.roots[self.root(x)]=self.root(y)
                #self.allunite(self.root(x),self.root(y))
            else:
                #self.dict[self.root(x)]=self.dict[self.root(x)]+self.dict[self.root(y)]
                #self.dict[self.root(y)]=[]
                self.roots[self.root(y)]=self.root(x)
                #self.allunite(self.root(y),self.root(x))
    

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

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train.unite(r-1,s-1)



count=defaultdict(lambda:0)
for i in range(N):
    a=road.root(i)
    b=train.root(i)
    l=[a,b]
    count[str(l)]+=1
for i in range(N):
    a=road.root(i)
    b=train.root(i)
    l=[a,b]
    print(count[str(l)],end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
class Unionfind:
    def __init__(self,n):
        self.n=n
        self.roots=[]
        self.dict=defaultdict(lambda:[])

        for i in range(self.n):
            self.roots.append(i)
            self.dict[i].append(i)

    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            if self.root(x)>self.root(y):
                self.dict[self.root(y)]=self.dict[self.root(y)]+self.dict[self.root(x)]
                self.dict[self.root(x)]=[]
                self.roots[self.root(x)]=self.root(y)
                self.allunite(self.root(x),self.root(y))
            else:
                self.dict[self.root(x)]=self.dict[self.root(x)]+self.dict[self.root(y)]
                self.dict[self.root(y)]=[]
                self.roots[self.root(y)]=self.root(x)
                self.allunite(self.root(y),self.root(x))
    def find(self,x):
        return self.dict[x]

    def allunite(self,x,y):
        unit=self.find(x)
        for i in range(len(unit)):
            self.roots[unit[i]]=y
            return
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train.unite(r-1,s-1)


road_g=road.roots
train_g=train.roots

count=defaultdict(lambda:0)
for i in range(N):
    l=[road_g[i],train_g[i]]
    count[str(l)]+=1
for i in range(N):
    l=[road_g[i],train_g[i]]
    print(count[str(l)],end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
class Unionfind:
    def __init__(self,n):
        self.n=n
        self.roots=[i for i in range(self.n)]
    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            if self.root(x)>self.root(y):
                self.roots[self.root(x)]=self.root(y)
                self.allunite(self.root(x),self.root(y))
            else:
                self.roots[self.root(y)]=self.root(x)
                self.allunite(self.root(y),self.root(x))
    def find(self,x):
        unit=[]
        for i in range(self.n):
            if x==self.roots[i]:
                unit.append(i)
        return unit
    def allunite(self,x,y):
        unit=self.find(x)
        for i in range(len(unit)):
            self.roots[unit[i]]=y
            return
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train.unite(r-1,s-1)


road_g=road.roots
train_g=train.roots

count=defaultdict(lambda:0)
for i in range(N):
    l=[road_g[i],train_g[i]]
    count[str(l)]+=1
for i in range(N):
    l=[road_g[i],train_g[i]]
    print(count[str(l)],end=" ")