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:
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())
road = UnionFind(N)
train = UnionFind(N)

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

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

ans = [0]*N
for k in range(N):
    if ans[k] != 0:
        pass
    else:
        t = set(road.members(k)) & set(train.members(k))
        for e in t:
            ans[e] = len(t)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
class UnionFind:


    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))
    def sameset(self):
        ret = defaultdict(set)
        for i in range(self.n):
            ret[self.find(i)] = ret[self.find(i)] | {i}
        return ret

from sys import stdin
def main():
    N,K,L = map(int,stdin.readline().split())
    uf = UnionFind(N)
    uf1 = UnionFind(N)
    ans = [0 for _ in range(N)]
    for _ in range(K):
        p,q = map(int,stdin.readline().split())
        uf.union(p-1,q-1)
    for _ in range(L):
        r,s = map(int,stdin.readline().split())
        if not uf.same(s-1,r-1):continue
        uf1.union(r-1,s-1)
    a = uf.sameset()
    b = uf1.sameset()
    for u in b.values():
        for v in a.values():
            tmp = list(u&v)
            if tmp:
                l = len(tmp)
                for j in tmp:
                    ans[j] += l
            else:continue
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
class UnionFind:


    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))
    def sameset(self):
        ret = defaultdict(set)
        for i in range(self.n):
            ret[self.find(i)] = ret[self.find(i)] | {i}
        return ret

from sys import stdin
def main():
    N,K,L = map(int,stdin.readline().split())
    uf = UnionFind(N)
    uf1 = UnionFind(N)
    ans = [0 for _ in range(N)]
    for _ in range(K):
        p,q = map(int,stdin.readline().split())
        uf.union(p-1,q-1)
    for _ in range(L):
        r,s = map(int,stdin.readline().split())
        uf1.union(r-1,s-1)
    a = uf.sameset()
    b = uf1.sameset()
    for u in a.values():
        for v in b.values():
            tmp = list(u&v)
            if tmp:
                l = len(tmp)
                for j in tmp:
                    ans[j] += l
            else:continue
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 32


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N, K, L = lmi()
pq = llmi(K)
rs = llmi(L)


class _UnionFind(object):
    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())


class UnionFind(_UnionFind):
    pass


uf_road = UnionFind(N)
for p, q in pq:
    uf_road.union(p - 1, q - 1)
uf_train = UnionFind(N)
for p, q in rs:
    uf_train.union(p - 1, q - 1)
road_dict = collections.defaultdict(set)  # parent node -> set of member
train_dict = collections.defaultdict(set)
for i in range(N):
    road_dict[uf_road.find(i)].add(i)
    train_dict[uf_train.find(i)].add(i)

print(' '.join(str(len(road_dict[uf_road.find(i)]&train_dict[uf_train.find(i)])) for i in range(N)))

Submission status: Time Limit Exceeded

Solution code:
N,K,L = map(int,input().split())
class UnionFind:
    def __init__(self, n):
        #ノード数nの配列を作る
        #親の番号を格納する
        #-> 自分が根だった場合は、-(その集合のサイズ)とする
        #作るときはparentの値を全て-1にする
        #初期化においては全ての要素がバラバラな森を表す
        self.parent = [-1 for _ in range(n)]
        self.n = n
    def root(self, x): #要素xの根の番号を返す
        if self.parent[x] < 0: # 自分が根のとき
            return x
        else:
            # 次の呼び出しの高速化
            self.parent[x] = self.root(self.parent[x]) # 要素xの親を要素xの根に変えておく(付け替える)
            return self.parent[x]
    def size(self, x): # 要素xの所属するグループの要素数を調べる
        return -self.parent[self.root(x)] #根のparentにサイズが格納されている
    def merge(self, x, y): #xとyを結合する
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False # そもそも結合されていたのでFalse
        if self.parent[x] > self.parent[y]: # 大きい方(x)に小さい方(y)をくっつけたい
            x, y = y, x # swapする
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        return True # 結合できたのでTrue
    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
    def family(self,x): # xが属する連結集合を返す
        return [i for i in range(self.n) if self.issame(i,x)]
    def maximum(self): # 連結最大集合を返す
        return self.family(self.parent.index(min(self.parent)))
    def all_root(self): # 全ての根の番号を返す
        return [i for i in range(self.n) if self.parent < 0]
    def decompose(self): # 連結成分分解(分類は根を基準とする)を返す
        R = {} # 根のindexの集合はlist(R.keys())で取得できる．これは根iが何番目の根かを返すdict
        now = 0
        for i in range(self.n):
            if self.parent[i] < 0:
                R[i] = now
                now += 1
        C = [[] for _ in range(len(R))] # i(根) -> R[i](根に振った番号) -> C[R[i]](根をiとする要素の集合)
        for i in range(self.n):
            C[R[self.root(i)]].append(i)
        return R, C # 根の辞書R(ノード番号から根番号への関数), 連結成分分解C(根をiとする要素全体の集合がC[R[i]])
UFK = UnionFind(N)
UFL = UnionFind(N)
for i in range(K):
    p,q = map(int,input().split())
    UFK.merge(p-1,q-1)
for i in range(L):
    r,s = map(int,input().split())
    UFL.merge(r-1,s-1)

RR,RC = UFK.decompose()
TR,TC = UFL.decompose()


ans = []
for i in range(N):
    ans.append(len(set(RC[RR[UFK.root(i)]]).intersection(set(TC[TR[UFL.root(i)]]))))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N,K,L = map(int,input().split())
class UnionFind:
    def __init__(self, n):
        #ノード数nの配列を作る
        #親の番号を格納する
        #-> 自分が根だった場合は、-(その集合のサイズ)とする
        #作るときはparentの値を全て-1にする
        #初期化においては全ての要素がバラバラな森を表す
        self.parent = [-1 for _ in range(n)]
        self.n = n
    def root(self, x): #要素xの根の番号を返す
        if self.parent[x] < 0: # 自分が根のとき
            return x
        else:
            # 次の呼び出しの高速化
            self.parent[x] = self.root(self.parent[x]) # 要素xの親を要素xの根に変えておく(付け替える)
            return self.parent[x]
    def size(self, x): # 要素xの所属するグループの要素数を調べる
        return -self.parent[self.root(x)] #根のparentにサイズが格納されている
    def merge(self, x, y): #xとyを結合する
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False # そもそも結合されていたのでFalse
        if self.parent[x] > self.parent[y]: # 大きい方(x)に小さい方(y)をくっつけたい
            x, y = y, x # swapする
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        return True # 結合できたのでTrue
    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
    def family(self,x): # xが属する連結集合を返す
        return [i for i in range(self.n) if self.issame(i,x)]
    def maximum(self): # 連結最大集合を返す
        return self.family(self.parent.index(min(self.parent)))
    def all_root(self): # 全ての根の番号を返す
        return [i for i in range(self.n) if self.parent < 0]
    def decompose(self): # 連結成分分解(分類は根を基準とする)を返す
        R = {} # 根のindexの集合はlist(R.keys())で取得できる．これは根iが何番目の根かを返すdict
        now = 0
        for i in range(self.n):
            if self.parent[i] < 0:
                R[i] = now
                now += 1
        C = [[] for _ in range(len(R))] # i(根) -> R[i](根に振った番号) -> C[R[i]](根をiとする要素の集合)
        for i in range(self.n):
            C[R[self.root(i)]].append(i)
        return R, C # 根の辞書R(ノード番号から根番号への関数), 連結成分分解C(根をiとする要素全体の集合がC[R[i]])
UFK = UnionFind(N)
UFL = UnionFind(N)
for i in range(K):
    p,q = map(int,input().split())
    UFK.merge(p-1,q-1)
for i in range(L):
    r,s = map(int,input().split())
    UFL.merge(r-1,s-1)

ans = []
for i in range(N):
    ans.append(len(set(UFK.family(i)).intersection(set(UFL.family(i)))))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:


def main():
    import sys
    input = sys.stdin.readline

    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))

    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        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):
            arr=[]
            for r in range(self.roots()):
                arr.append(set(self.members(r)))
            return arr

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
################
    mod=10**9+7
    N,K,L=MI()
    uf1 = UnionFind(N)
    uf2 = UnionFind(N)
    ans=[0]*N

    for i in range(K):
        p,q=MI()
        p-=1
        q-=1
        uf1.union(p,q)
        
    for i in range(L):
        p,q=MI()
        p-=1
        q-=1
        uf2.union(p,q)
        
    g1=[]
    map1=[0]*N#どのグループに所属するかメモしておく
    for i in uf1.roots():
        A=set([])
        for j in uf1.members(i):
            A.add(j)
            map1[j]=len(g1)
        g1.append(A)
        
    g2=[]
    map2=[0]*N#どのグループに所属するかメモしておく
    for i in uf2.roots():
        A=set([])
        for j in uf2.members(i):
            A.add(j)
            map2[j]=len(g2)
        g2.append(A)
    
    
    
    
        
        
    for i in range(N):
        if ans[i]==0:
            A=g1[map1[i]]
            B=g2[map2[i]]
            C=A&B
            g1[map1[i]]-=C
            g2[map1[i]]-=C
            
            C=list(C)
            NC=len(C)
            for i in range(NC):
                ans[C[i]]=NC
                
    print(' '.join(map(str, ans)))
        
        
    


main()

Submission status: Time Limit Exceeded

Solution code:


def main():
    import sys
    input = sys.stdin.readline

    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))

    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        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())
    
################
    mod=10**9+7
    N,K,L=MI()
    uf1 = UnionFind(N)
    uf2 = UnionFind(N)
    ans=[0]*N

    for i in range(K):
        p,q=MI()
        p-=1
        q-=1
        uf1.union(p,q)
        
    for i in range(L):
        p,q=MI()
        p-=1
        q-=1
        uf2.union(p,q)
        
    for i in range(N):
        if ans[i]==0:
            A=set(uf1.members(i))
            B=set(uf2.members(i))
            C=list(A&B)
            NC=len(C)
            for i in range(NC):
                ans[C[i]]=NC
                
    print(' '.join(map(str, ans)))
        
        
    


main()

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

################
class UnionFind():
    """
    parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
    find(x):要素xの属するグループの根を返す
    size(x):要素xの属するグループの要素数を返す
    same(x,y):x,yが同じグループに属しているか返す
    members(x):要素xが属するグループに属する要素をリストで返す
    roots:全ての根の要素を返す
    group_count():グループの数を返す
    all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
    """
    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())
    
################

def main():
    mod=10**9+7
    N,K,L=MI()
    uf1 = UnionFind(N)
    uf2 = UnionFind(N)
    ans=[0]*N

    for i in range(K):
        p,q=MI()
        p-=1
        q-=1
        uf1.union(p,q)
        
    for i in range(L):
        p,q=MI()
        p-=1
        q-=1
        uf2.union(p,q)
        
    for i in range(N):
        if ans[i]==0:
            A=set(uf1.members(i))
            B=set(uf2.members(i))
            C=list(A&B)
            NC=len(C)
            for i in range(NC):
                ans[C[i]]=NC
                
    print(' '.join(map(str, ans)))
        
        
    


main()

Submission status: Time Limit Exceeded

Solution code:
N,K,L=map(int,input().split())
p=[0 for k in range(K)]
q=[0 for k in range(K)]
r=[0 for k in range(L)]
s=[0 for k in range(L)]
for k in range(K):
    p[k],q[k]=map(int,input().split())
for k in range(L):
    r[k],s[k]=map(int,input().split())
car=[0 for k in range(N)]
train=[0 for k in range(N)]
car[p[0]-1]=1
car[q[0]-1]=1
n=1
for k in range(K):
    if car[p[k]-1]!=n:
        car[p[k]-1]=n+1
        n+=1
    for j in range(K):
        if p[j]==q[k]:
            car[q[j]-1]=n
        if q[j]==q[k]:
            car[p[j]-1]=n
car[q[K-1]-1]=n
train[r[0]-1]=1
train[s[0]-1]=1
m=1
for k in range(L):
    if train[r[k]-1]!=m:
        train[r[k]-1]=m+1
        m+=1
    for j in range(L):
        if r[j]==s[k]:
            train[s[j]-1]=m
        if s[j]==s[k]:
            train[r[j]-1]=m
train[s[L-1]-1]=m
for k in range(N):
    train[k]=train[k]*(n+1)
ans=[1 for k in range(N)]
lis=[0 for k in range(N)]
for k in range(N):
    lis[k]=train[k]+car[k]
for k in range(N-1):
    if lis[k]>n+1:
        for j in range(k+1,N):
            if lis[k]==lis[j]:
                ans[j]+=1
                ans[k]+=1
print(" ".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
N, K, L = map(int,input().split())
data = [[0, 0] for _ in range(N)]
Lpath = [[] for _ in range(N)]
Tpath = [[] for _ in range(N)]

for _ in range(K):
    p, q = map(int,input().split())
    p -= 1
    q -= 1
    Lpath[p].append(q)
    Lpath[q].append(p)
    
for _ in range(L):
    r, s = map(int,input().split())
    r -= 1
    s -= 1
    Tpath[r].append(s)
    Tpath[s].append(r)
    
for i in range(N):
    if data[i][0]:
        continue
    data[i][0] = i + 1
    stack = [i]
    while stack:
        s = stack.pop()
        for to in Lpath[s]:
            if data[to][0]:
                continue
            data[to][0] = i + 1
            stack.append(to)

for i in range(N):
    if data[i][1]:
        continue
    data[i][1] = i + 1
    stack = [i]
    while stack:
        s = stack.pop()
        for to in Tpath[s]:
            if data[to][1]:
                continue
            data[to][1] = i + 1
            stack.append(to)

ans = [0] * N
            
for i in range(N):
    ans[i] = data.count(data[i])

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())

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

for _ in range(k):
  p, q = map(lambda x:int(x)-1, input().split())
  uf_road.Unite(p, q)

for _ in range(l):
  r, s = map(lambda x:int(x)-1, input().split())
  uf_train.Unite(r, s)

for i in range(n):
  road_member = set(uf_road.Members(i))
  train_member = set(uf_train.Members(i))
  print(len(road_member&train_member), end=" ")

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())

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

for _ in range(k):
  p, q = map(lambda x:int(x)-1, input().split())
  uf_road.Unite(p, q)

for _ in range(l):
  r, s = map(lambda x:int(x)-1, input().split())
  uf_train.Unite(r, s)

for i in range(n):
  road_member = set(uf_road.Members(i))
  train_member = set(uf_train.Members(i))
  print(len(road_member&train_member), end=" ")

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, elements):
        self.elements = {e: -1 for e in elements}

    def same(self, a, b):
        return self.find(a) == self.find(b)

    def find(self, a):
        parent = self.elements[a]
        if parent < 0:
            return a
        self.elements[a] = self.find(parent)
        return self.elements[a]

    def unite(self, a, b):
        a_parent = self.find(a)
        b_parent = self.find(b)

        # already same union
        if a_parent == b_parent:
            return

        self.elements[a_parent] += self.elements[b_parent]
        self.elements[b_parent] = a_parent


N, K, L = map(int, input().split())
roads = []
trains = []
for _ in range(K):
    roads.append(list(map(int, input().split())))
for _ in range(L):
    trains.append(list(map(int, input().split())))

road_union = UnionFind(i for i in range(1, N + 1))
for road in roads:
    road_union.unite(road[0], road[1])

train_union = UnionFind(i for i in range(1, N + 1))
for train in trains:
    train_union.unite(train[0], train[1])

ma = dict()
for i in range(N):
    p = (road_union.find(i + 1), train_union.find(i + 1))
    ma.setdefault(p, 0)
    ma[p] += 1

for i in range(N):
    p = (road_union.find(i + 1), train_union.find(i + 1))
    print(ma[p], end=' ')

Submission status: Time Limit Exceeded

Solution code:

class UnionFind():
    def __init__(self,n):
        self.n = n
        #self.root < 0 であれば根で、かつ絶対値が要素数。
        self.root = [-1]*(n+1)
        self.rank = [0]*(n+1)

    def findroot(self,x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.findroot(self.root[x])
            return self.root[x]
    
    def unite(self,x,y):
        x = self.findroot(x)
        y = self.findroot(y)
        if x == y:
            return
        elif self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x]==self.rank[y]:
                self.rank[x] += 1
    
    def groupjudge(self,x,y):
        return self.findroot(x)==self.findroot(y)
        
    def count(self,x):
        return -self.root[self.findroot(x)]

##arc065d

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

for i in range(k):
    c,d = map(int,input().split())
    load.unite(c,d)

for i in range(l):
    p,q = map(int,input().split())
    rail.unite(p,q)

out = []

for i in range(n):
    lres = []
    for j in range(n):
        if load.findroot(i+1) == load.findroot(j+1):
            lres.append(j+1)
    rres = []
    for j in range(n):
        if rail.findroot(i+1) == rail.findroot(j+1):
            rres.append(j+1)
    lres = set(lres)
    rres = set(rres)
    out.append(len(lres & rres))

print(" ".join(map(str,out)))

Submission status: Time Limit Exceeded

Solution code:

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.node_size = 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_list = set([x for x in range(self.node_size) if self.parent[x] == root_node])
            self.member_dict[root_node] = group_list
            return group_list


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)