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 collections


class UnitDict(dict):

    def __init__(self, iterable=None, wrapper=lambda x: x):
        super().__init__(self)
        self.wrapper = wrapper
        if iterable is not None:
            self.update(iterable)

    def __missing__(self, key):
        self[key] = self.wrapper(key)
        return self[key]


class UnionFind(object):

    def __init__(self, nodes=None):
        self.par = UnitDict(wrapper=lambda x: x)
        self.rank = collections.defaultdict(int)
        self.groups = UnitDict(wrapper=lambda x: {x})
        if nodes is not None:
            for node in nodes:
                _, _, _ = self.par[node], self.rank[node], self.groups[node]

    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r

    def are_same(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def elements(self, node):
        return self.groups[self.root(node)]

    def size(self, node):
        return len(self.elements(node))

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            self.groups[x].update(self.groups[y])
            self.groups[y].clear()
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def grouper(self):
        roots = [x for x in self.par.keys()]
        groups = []
        for root in roots:
            if list(self.elements(root)) not in groups:
                groups.append(list(self.elements(root)))
        return groups


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


graph_road = UnionFind(range(N))
graph_train = UnionFind(range(N))
for p, q in PQ:
    graph_road.unite(p-1, q-1)

for r, s in RS:
    graph_train.unite(r-1, s-1)

for i in range(N):
    ans = 0
    road = graph_road.elements(i)
    train = graph_train.elements(i)
    ans += len(set(road) & set(train))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K, L = map(int, input().split())
pq = [map(int, input().split()) for _ in range(K)]
rs = [map(int, input().split()) for _ in range(L)]

class UnionFind:
    def __init__(self, N):
        self.par = [n for n in range(N+1)]

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

    def union(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.par[rx] = ry

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

uf_road = UnionFind(N)
uf_train = UnionFind(N)

for p, q in pq:
    uf_road.union(p, q)
for r, s in rs:
    uf_train.union(r, s)

from collections import Counter
c = Counter()
for i in range(1, N+1):
    k = (uf_road.root(i), uf_train.root(i))
    c[k] += 1

ret = []
for i in range(1, N+1):
    k = (uf_road.root(i), uf_train.root(i))
    ret.append(c[k])

print(" ".join(str(v) for v in ret))

Submission status: Time Limit Exceeded

Solution code:
class UnionFindTree():
    def __init__(self, values=[]):
        self.__parent_of = {}
        self.__rank_of = {}
        self.__size = {}
        for value in values:
            self.add(value)

    def add(self, value):
        if value in self.__parent_of:
            raise RuntimeError("Dupulicated Value Added")
        self.__parent_of[value] = None
        self.__rank_of[value] = 0
        self.__size[value] = 1

    def __root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.__root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.__root(a)
        r2 = self.__root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.__root(a) == self.__root(b)

    def size(self, a):
        return self.__size[self.__root(a)]

    def groups(self):
        groups = {}
        for k in self.__parent_of.keys():
            r = self.__root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, K, L = map(int, input().split())
    uft = UnionFindTree(range(N))
    for _ in range(K):
        p, q = map(int, input().split())
        uft.unite(p-1, q-1)
    uft2 = UnionFindTree(range(N))
    for _ in range(L):
        r, s = map(int, input().split())
        uft2.unite(r-1, s-1)
    pair = [(0, 0)] * N
    cnt = {}
    for i in range(N):
        r1 = uft._UnionFindTree__root(i)
        r2 = uft2._UnionFindTree__root(i)
        if (r1, r2) not in cnt:
            cnt[(r1, r2)] = 0
        cnt[(r1, r2)] += 1
        pair[i] = (r1, r2)
    ans = [0] * N
    for i in range(N):
        ans[i] = cnt[pair[i]]
    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFindTree():
    def __init__(self, values=[]):
        self.__parent_of = {}
        self.__rank_of = {}
        self.__size = {}
        for value in values:
            self.add(value)

    def add(self, value):
        if value in self.__parent_of:
            raise RuntimeError("Dupulicated Value Added")
        self.__parent_of[value] = None
        self.__rank_of[value] = 0
        self.__size[value] = 1

    def __root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.__root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.__root(a)
        r2 = self.__root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.__root(a) == self.__root(b)

    def size(self, a):
        return self.__size[self.__root(a)]

    def groups(self):
        groups = {}
        for k in self.__parent_of.keys():
            r = self.__root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, K, L = map(int, input().split())
    uft = UnionFindTree(range(N))
    for _ in range(K):
        p, q = map(int, input().split())
        uft.unite(p-1, q-1)
    uft2 = UnionFindTree(range(N))
    for _ in range(L):
        r, s = map(int, input().split())
        uft2.unite(r-1, s-1)
    pair = [(0, 0)] * N
    cnt = {}
    for i in range(N):
        r1 = uft._UnionFindTree__root(i)
        r2 = uft2._UnionFindTree__root(i)
        if (r1, r2) not in cnt:
            cnt[(r1, r2)] = 0
        cnt[(r1, r2)] += 1
    ans = [0] * N
    for i in range(N):
        r1 = uft._UnionFindTree__root(i)
        r2 = uft2._UnionFindTree__root(i)
        ans[i] = cnt[(r1, r2)]
    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
    def find(self, x):
        if self.par[x] == x:
          return x
        else:
          self.par[x] = self.find(self.par[x])
          return self.find(self.par[x])
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

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

for i in range(k):
  x, y = map(int, input().split())
  uf1.union(x-1, y-1)
for i in range(l):
  x, y = map(int, input().split())
  uf2.union(x-1, y-1)

pair = [[uf1.find(i), uf2.find(i)] for i in range(n)]

ans = [pair.count(i) for i in pair]

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

Submission status: Time Limit Exceeded

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
    def find(self, x):
        if self.par[x] == x:
          return x
        else:
          self.par[x] = self.find(self.par[x])
          return self.find(self.par[x])
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

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

for i in range(k):
  x, y = map(int, input().split())
  uf1.union(x-1, y-1)
for i in range(l):
  x, y = map(int, input().split())
  uf2.union(x-1, y-1)

ans = [1] * n

for i in range(1, n):
  for j in range(i):
    if uf1.is_same(i, j) and uf2.is_same(i, j):
      ans[i] += 1
      ans[j] += 1

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

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

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

        return self.p[x]

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

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

        if u == v: return

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

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

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


n, K, L = map(int, input().split())
pq = [tuple(int(x)-1 for x in input().split()) for _ in range(K)]
rs = [tuple(int(x)-1 for x in input().split()) for _ in range(L)]

uk = UnionFind(n)
for p, q in pq:
    uk.unite(p, q)

ul = UnionFind(n)
for p, q in rs:
    ul.unite(p, q)

res = [tuple([uk.find_root(i), ul.find_root(i)]) for i in range(n)]

ans = ['' for _ in range(n)]
for i in range(n):
    ans[i] = str(res.count(res[i]))

print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:


import collections
import itertools
import operator


class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

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

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]

uf = UnionFind()
tf = UnionFind()
n,k,l =  map(int, input().split())
dp =[1]*n
for i in range(k):
    x,y =map(int, input().split())
    uf.unite(x-1, y-1)  # (3)
for i in range(l):
    x,y =map(int, input().split())
    tf.unite(x-1, y-1)  # (3)
for i in range(n):
    for j in range(i+1,n):
        if uf.are_same(i,j) and tf.are_same(i,j):
            dp[i]+=1
            dp[j]+=1
print(" ".join(map(str, dp)))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

class UnionFind:
    def __init__(self, size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]

    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x

    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]


n, K, L = map(int, input().split())
pq = [tuple(int(x) for x in input().split()) for _ in range(K)]
rs = [tuple(int(x) for x in input().split()) for _ in range(L)]

uk = UnionFind(n)
for p, q in pq:
    rp = uk.find(p - 1)
    rq = uk.find(q - 1)
    if rp != rq:
        uk.union(rp, rq)

ul = UnionFind(n)
for p, q in rs:
    rp = ul.find(p - 1)
    rq = ul.find(q - 1)
    if rp != rq:
        ul.union(rp, rq)

res = [tuple([uk.find(i), ul.find(i)]) for i in range(n)]

#c = Counter(res)

#print(c)
ans = ['' for _ in range(n)]
for i in range(n):
    ans[i] = str(res.count(res[i]))

print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]

    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x

    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]


n, K, L = map(int, input().split())
pq = [tuple(int(x) for x in input().split()) for _ in range(K)]
rs = [tuple(int(x) for x in input().split()) for _ in range(L)]

uk = UnionFind(n)
for p, q in pq:
    rp = uk.find(p - 1)
    rq = uk.find(q - 1)
    if rp != rq:
        uk.union(rp, rq)

ul = UnionFind(n)
for p, q in rs:
    rp = ul.find(p - 1)
    rq = ul.find(q - 1)
    if rp != rq:
        ul.union(rp, rq)

res = [[uk.find(i), ul.find(i)] for i in range(n)]

ans = ['' for _ in range(n)]
for i in range(n):
    ans[i] = str(res.count(res[i]))

print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]

    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x

    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]


n, K, L = map(int, input().split())
pq = [tuple(int(x) for x in input().split()) for _ in range(K)]
rs = [tuple(int(x) for x in input().split()) for _ in range(L)]

uk = UnionFind(n)
for p, q in pq:
    rp = uk.find(p - 1)
    rq = uk.find(q - 1)
    if rp != rq:
        uk.union(rp, rq)

ul = UnionFind(n)
for p, q in rs:
    rp = ul.find(p - 1)
    rq = ul.find(q - 1)
    if rp != rq:
        ul.union(rp, rq)

ans = ['' for _ in range(n)]
for i in range(n):
    temp = 0
    for j in range(n):
        if uk.find(i) == uk.find(j) and ul.find(i) == ul.find(j):
            temp += 1
    ans[i] = str(temp)

print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]

    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x

    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]


n, K, L = map(int, input().split())
pq = [tuple(int(x) for x in input().split()) for _ in range(K)]
rs = [tuple(int(x) for x in input().split()) for _ in range(L)]

uk = UnionFind(n)
for p, q in pq:
    rp = uk.find(p - 1)
    rq = uk.find(q - 1)
    if rp != rq:
        uk.union(rp, rq)

ul = UnionFind(n)
for p, q in rs:
    rp = ul.find(p - 1)
    rq = ul.find(q - 1)
    if rp != rq:
        ul.union(rp, rq)

ans = ['' for _ in range(n)]
for i in range(n):
    temp = 0
    for j in range(n):
        if uk.find(i) == uk.find(j) and ul.find(i) == ul.find(j):
            #print(uk.find(i), uk.find(j), ul.find(i), ul.find(j), i, j)
            temp += 1
    ans[i] = str(temp)

print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
n,k,l= map(int, input().split())
rom= [i for i in range(n+1)]
rot=[i for i in range(n+1)]
unim=[[i] for i in range(n+1)]
unit=[[i] for i in range(n+1)]

for i in range(k):
    a=0
    b=0
    p,q=map(int,input().split())
    if len(unim[rom[p]])<len(unim[rom[q]]):
        a=q
        b=p
    else:
        a=p
        b=q
        
    unim[rom[a]]+=unim[rom[b]]
    for j in unim[rom[b]]:
        rom[j]=rom[a]
      
for i in range(l):
    a=0
    b=0
    p,q=map(int,input().split())

    if len(unit[rot[p]])<len(unit[rot[q]]):
        a=q
        b=p
    else:
        a=p
        b=q
    unit[rot[a]]+=unit[rot[b]] 
    for j in unit[rot[b]]:
        rot[j]=rot[a]   

for i in range(n-1):
    print(len(set(unim[rom[i+1]]) & set(unit[rot[i+1]])),end=' ')
print(len(set(unim[rom[n]]) & set(unit[rot[n]])))

Submission status: Time Limit Exceeded

Solution code:
n,k,l= map(int, input().split())
rom= [i for i in range(n+1)]
rot=[i for i in range(n+1)]
unim=[[i] for i in range(n+1)]
unit=[[i] for i in range(n+1)]

for i in range(k):
    p,q=map(int,input().split())
    if len(unim[rom[p]])<len(unim[rom[q]]):
        a=q
        b=p
    else:
        a=p
        b=q
        
    unim[rom[a]]+=unim[rom[b]]
    for j in unim[rom[b]]:
        rom[j]=rom[a]
      
for i in range(l):
    p,q=map(int,input().split())

    if len(unit[rot[p]])<len(unit[rot[q]]):
        a=q
        b=p
    else:
        a=p
        b=q
    unit[rot[a]]+=unit[rot[b]] 
    for j in unit[rot[b]]:
        rot[j]=rot[a]   

for i in range(n-1):
    print(len(set(unim[rom[i+1]]) & set(unit[rot[i+1]])),end=' ')
print(len(set(unim[rom[n]]) & set(unit[rot[n]])))

Submission status: Time Limit Exceeded

Solution code:
n,k,l= map(int, input().split())
rom= [i for i in range(n+1)]
rot=[i for i in range(n+1)]
unim=[[i] for i in range(n+1)]
unit=[[i] for i in range(n+1)]

for i in range(k):
    a,b=map(int,input().split())
    unim[rom[a]]+=unim[rom[b]]
    for j in unim[rom[b]]:
        rom[j]=rom[a]
      
for i in range(l):
    a,b=map(int,input().split())
    unit[rot[a]]+=unit[rot[b]] 
    for j in unit[rot[b]]:
        rot[j]=rot[a]   

for i in range(n-1):
    print(len(set(unim[rom[i+1]]) & set(unit[rot[i+1]])),end=' ')
print(len(set(unim[rom[n]]) & set(unit[rot[n]])))

Submission status: Time Limit Exceeded

Solution code:
n,k,l= map(int, input().split())
rom= [i for i in range(n+1)]
rot=[i for i in range(n+1)]
unim=[[i] for i in range(n+1)]
unit=[[i] for i in range(n+1)]

for i in range(k):
    a,b=map(int,input().split())
    unim[rom[a]]+=unim[rom[b]]
    for j in unim[rom[b]]:
        rom[j]=rom[a]
      
for i in range(l):
    a,b=map(int,input().split())
    unit[rot[a]]+=unit[rot[b]] 
    for j in unit[rot[b]]:
        rot[j]=rot[a]   

for i in range(n-1):
    print(len(set(unim[rom[i+1]]) & set(unit[rot[i+1]])),end=' ')
print(len(set(unim[rom[n]]) & set(unit[rot[n]])))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,K,L=map(int,input().split())
road=[tuple(map(int,input().split())) for _ in range(K)]
metro=[tuple(map(int,input().split())) for _ in range(L)]
inf=float('inf')
def Find(root,x):
    if root[x]<0:
        return x
    if root[x]>=0:
        root[x]=Find(root,root[x])
    return root[x]

def UnionFind(N,branch):
    root=[-1*inf]*(N+1)
    tree=dict()
    for a,b in branch:
        aroot=Find(root,a)
        broot=Find(root,b)
        if root[aroot]<-1*N and root[broot]<-1*N:
            tree[-1*a]={a,b}
            root[a]=-1*a
            root[b]=a
        elif root[broot]<-1*N and root[aroot]>=-1*N:
            tree[root[aroot]]|={b,}
            root[broot]=aroot
        elif root[aroot]<-1*N and root[broot]>=-1*N:
            tree[root[broot]]|={a,}
            root[aroot]=broot
        elif root[aroot]==root[broot]:
            continue
        elif root[aroot]!=root[broot]:
            tree[root[aroot]]|=tree[root[broot]]
            tree.pop(root[broot])
            root[broot]=aroot
    return root,tree

r_root,r_tree=UnionFind(N,road)
m_root,m_tree=UnionFind(N,metro)
ans=''
for i in range(1,N+1):
    ri=Find(r_root,i)
    mi=Find(m_root,i)
    if r_root[ri]<-1*N or m_root[mi]<-1*N:
        ans+='1 '
    else:
        ans+=str(len(r_tree[r_root[ri]]&m_tree[m_root[mi]]))+' '
print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n

    def get_root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.get_root(self.table[x])
            return self.table[x]

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

    def union(self, x, y):
        r1 = self.get_root(x)
        r2 = self.get_root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2

N, K, L = map(int, input().split())
tree1 = UnionFind(N+1)
tree2 = UnionFind(N+1)

for _ in range(K):
    i, j = map(int, input().split())
    tree1.union(i, j)
for _ in range(L):
    i, j = map(int, input().split())
    tree2.union(i, j)

ans = []
for i in range(1, N+1):
    a = 0
    for j in range(1, N+1):
        if tree1.find(i, j) == True and tree2.find(i, j) == True:
            a += 1
    ans.append(a)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:

par1 , rank1 = [],[] 
par2 , rank2 = [],[]


def find(x,par,rank):
    if par[x] == x : return x
    else:
        par[x] = find(par[x],par,rank)
        return par[x]

def unite(x,y,par,rank): 
    x = find(x,par,rank)
    y = find(y,par,rank)
    if (x != y):
        if rank[x] < rank[y]:
            par[x] = y
        else :
            par[y] = x
            if (rank[x] == rank[y]) : rank[x] += 1

def same(x,y,par,rank):
    return (find(x,par,rank) == find(y,par,rank)) 

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

for i in range(n): 
    par1.append(i)
    rank1.append(0)
    par2.append(i)
    rank2.append(0)

for i in range(k):
    pp,qq = map(int,input().split())
    unite(pp-1,qq-1,par1,rank1)

for i in range(l):
    rr,ss = map(int,input().split())
    if (same(rr-1,ss-1,par1,rank1)) : unite(rr-1,ss-1,par2,rank2)

dic = {}
parlis = []
for i in range(n):
    p1 = find(i,par2,rank2)
    parlis.append(p1)
    if p1 in dic:
        dic[p1] += 1
    else: 
        dic[p1] = 1

ans = str(dic[parlis[0]])

for i in range(1,n):
    ans = ans + " " + str(dic[parlis[i]])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#UnionFindクラス
class UnionFind(object):

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

  def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
  
  # xとyの根を結合させる
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

n,k,l = map(int,input().split())
    
uf_road = UnionFind(n)
uf_rail = UnionFind(n)
for i in range(k):
  tmp1,tmp2 = map(int,input().split())
  uf_road.union(tmp1-1,tmp2-1)
  
for i in range(l):
  tmp1,tmp2 = map(int,input().split())
  uf_rail.union(tmp1-1,tmp2-1)

li = [[0]*n for i in range(n)]  
for i in range(n):
  li[uf_rail.find(i)][uf_road.find(i)] +=1

for i in range(n):
  print(li[uf_rail.find(i)][uf_road.find(i)],end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys
from collections import defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, k, l = LI()


def DFS(s, G, memo):
    q = [s]
    visited = set()
    while q:
        v = q.pop()
        visited.add(v)
        for nv in G[v]:
            if nv in visited:
                continue
            q.append(nv)

    for v in list(visited):
        memo[v] |= visited

    return memo


A = defaultdict(list)
B = defaultdict(list)
for _ in range(k):
    p, q = LI_()
    A[p].append(q)
    A[q].append(p)

for _ in range(l):
    r, s = LI_()
    B[r].append(s)
    B[s].append(r)


memo_a = defaultdict(set)
memo_b = defaultdict(set)

for i in range(n):
    if memo_a[i]:
        continue
    memo_a = DFS(i, A, memo_a)

for i in range(n):
    if memo_b[i]:
        continue
    memo_b = DFS(i, B, memo_b)

ans = []
for i in range(n):
    ans.append(len(memo_a[i] & memo_b[i]))

print(*ans)

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)

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

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

n,k,l = (int(i) for i in input().split())
ufr = UnionFind(n-1)
uft = UnionFind(n-1)
for i in range(k):
  tmp1,tmp2 = (int(i) for i in input().split())
  ufr.union(tmp1-1,tmp2-1)
for j in range(l):
  tmp1,tmp2 = (int(i) for i in input().split())
  if ufr.same_check(tmp1-1,tmp2-1):
   uft.union(tmp1-1,tmp2-1)

ans = [1]*n
for i in range(n):
  if uft.par.count(uft.par[i]) >= 2:
    ans[i] += uft.par.count(uft.par[i])-1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,k,l=map(int,input().split())
def maketree(n,k):
    from collections import defaultdict
    road=defaultdict(set)
    roadidx=[-1 for _ in range(n)]
    for i in range(k):
        p,q=map(int,input().split())
        p-=1
        q-=1
        pidx=roadidx[p]
        qidx=roadidx[q]
        if pidx==-1 and qidx==-1:
            road[p]={p,q}
            roadidx[p]=p
            roadidx[q]=p
        elif pidx==-1 and qidx!=-1:
            road[qidx]|={p,}
            roadidx[p]=qidx
        elif pidx!=-1 and qidx==-1:
            road[pidx]|={q,}
            roadidx[q]=pidx
        elif pidx!=qidx:
            road[pidx]=road[pidx]|road[qidx]
            for j in road[qidx]:
                roadidx[j]=pidx
            road.pop(qidx)
    return roadidx

def renew(idx):
    count=0
    for i in range(len(idx)):
        if idx[i]==-1:
            idx[i]-=count
            count+=1
    return idx
roadidx=renew(maketree(n,k))
metroidx=renew(maketree(n,l))


idx=[]
for i in range(n):
    idx.append((roadidx[i],metroidx[i]))
res=''
for i in range(n):
    res=res+str(idx.count(idx[i]))+' '
print(res)
###https://img.atcoder.jp/arc065/editorial.pdf