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:
def bellman_ford(num, start, adj):
    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    while 1:
        update = False
        for i,j,k in adj:
            if dist[j] > dist[i] + k:
                dist[j] = dist[i] + k
                update = True
            if dist[i] > dist[j] + k:
                dist[i] = dist[j] + k
                update = True
        if not update:
            break
    return dist
n,k,l = map(int, input().split(" "))
sum = [0 for i in range(n)]
adj_s = []
adj_t = []
ans_s = []
ans_t = []
for i in range(k):
    a,b= map(int, input().split(" "))
    adj_s.append([a-1,b-1,0])
for i in range(n):
    ans_s.append(bellman_ford(n, i, adj_s))

for i in range(l):
    a,b= map(int, input().split(" "))
    adj_t.append([a-1,b-1,0])
for i in range(n):
    ans_t.append(bellman_ford(n, i, adj_t))
for i in range(n):
    for j in range(n):
        if ans_s[i][j] != float("inf") and ans_t[i][j] != float("inf"):
            sum[i] += 1
            sum[j] += 1
for i in range(len(sum)-1):
    print(sum[i]//2,end = " ")
print(sum[len(sum)-1]//2)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations
import sys
sys.setrecursionlimit(10000)
def inpl(): return tuple(map(int, input().split()))
 
N, K, L = inpl()
 
tree = [[[-1, 1]  for _ in range(N+1)] for _ in range(2)] # [next, rank]

def find(i, t):
    if tree[t][i][0] == -1:
        group = i
    else:
        group = find(tree[t][i][0], t)
        tree[t][i][0] = group
    return group
 
def unite(x, y, t):
    px = find(x, t)
    py = find(y, t)
     
    if tree[t][px][1] == tree[t][py][1]: # rank is same
        tree[t][py][0] = px
        tree[t][px][1] += 1
    else:
        if tree[t][px][1] < tree[t][py][1]:
            px, py = py, px
        tree[t][py][0] = px
 
for _ in range(K):
    x, y = inpl()
    if not int(find(x, 0) == find(y, 0)):
        unite(x, y, 0)

for _ in range(L):
    x, y = inpl()
    if not int(find(x, 1) == find(y, 1)):
        unite(x, y, 1)

res = [1 for _ in range(N+1)]

for x, y in combinations(range(1, N+1), 2):
    if find(x, 0) == find(y, 0) and find(x, 1) == find(y, 1):
        res[x] += 1
        res[y] += 1

print(" ".join(map(str, res[1:])))

Submission status: Time Limit Exceeded

Solution code:
# 頂点 v の所属するグループを調べる
def root(v, uni):
  if uni[v] < 0:  # v が親の場合
    return v
  else:           # v が子の場合
    uni[v] = root(uni[v], uni)  # 親のrootを調べる
    return uni[v]

# 頂点 a と頂点 b をつなぐ。もともと同じグループのとき、False を返す
def connect(a, b, uni):
  # まずはそれぞれ根の番号に置き換える
  ra = root(a, uni)
  rb = root(b, uni)
  if ra == rb:  # a と b がそもそも同じグループに属しているなら即終了
    return False
  
  # ra と rb を結合し、rb の親を ra とする
  uni[rb] = ra
  return True


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

road = [0]*(N+1)
rail = [0]*(N+1)

for i in range(1, N+1):
  road[i] = -i
  rail[i] = -i

for i in range(K):
  a, b = map(int, input().split())
  connect(a, b, road)

for i in range(L):
  a, b = map(int, input().split())
  connect(a, b, rail)


##
dp = [0]*(N+1)
for i in range(1, N+1):
  dp[i] = (root(i, road), root(i, rail))

dic = {}
for i in range(1, N+1):
  key = dp[i]
  if key not in dic:
    dic[key] = 1
  else:
    dic[key] += 1

ans = ""
for i in range(1, N+1):
  tmp = dic[dp[i]]
  if i == 1:
    ans = str(tmp)
  else:
    ans += " " + str(tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 頂点 v の所属するグループを調べる
def root(v, uni):
  if uni[v] < 0:  # v が親の場合
    return v
  else:           # v が子の場合
    uni[v] = root(uni[v], uni)  # 親のrootを調べる
    return uni[v]

# 頂点 a と頂点 b をつなぐ。もともと同じグループのとき、False を返す
def connect(a, b, uni):
  # まずはそれぞれ根の番号に置き換える
  ra = root(a, uni)
  rb = root(b, uni)
  if ra == rb:  # a と b がそもそも同じグループに属しているなら即終了
    return False
  
  # ra と rb を結合し、rb の親を ra とする
  uni[rb] = ra
  return True


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

road = [0]*(N+1)
rail = [0]*(N+1)

for i in range(1, N+1):
  road[i] = -i
  rail[i] = -i

for i in range(K):
  a, b = map(int, input().split())
  connect(a, b, road)

for i in range(L):
  a, b = map(int, input().split())
  connect(a, b, rail)


##
dp = [0]*(N+1)
for i in range(1, N+1):
  dp[i] = (root(i, road), root(i, rail))

dic = {}
for i in range(1, N+1):
  key = dp[i]
  if key not in dic:
    dic[key] = 1
  else:
    dic[key] += 1

for i in range(1, N+1):
  ans = dic[dp[i]]
  if i == N:
    print(ans)
  else:
    print(ans, end=" ")

Submission status: Time Limit Exceeded

Solution code:
# 頂点 v の所属するグループを調べる
def root(v, uni):
  if uni[v] < 0:  # v が親の場合
    return v
  else:           # v が子の場合
    uni[v] = root(uni[v], uni)  # 親のrootを調べる
    return uni[v]

# 頂点 a と頂点 b をつなぐ。もともと同じグループのとき、False を返す
def connect(a, b, uni, sets):
  # まずはそれぞれ根の番号に置き換える
  ra = root(a, uni)
  rb = root(b, uni)
  if ra == rb:  # a と b がそもそも同じグループに属しているなら即終了
    return False
  
  # ra と rb を結合し、rb の親を ra とする
  sets[ra] = sets[ra] | sets[rb]
  uni[rb] = ra
  return True


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

road = [0]*(N+1)
rail = [0]*(N+1)

road_sets = [0]*(N+1)
rail_sets = [0]*(N+1)

for i in range(1, N+1):
  road[i] = -i
  rail[i] = -i
  road_sets[i] = set([i])
  rail_sets[i] = set([i])

for i in range(K):
  a, b = map(int, input().split())
  connect(a, b, road, road_sets)

for i in range(L):
  a, b = map(int, input().split())
  connect(a, b, rail, rail_sets)

for i in range(1, N+1):
  tmp = road_sets[root(i, road)] & rail_sets[root(i, rail)]
  ans = len(tmp)
  if i == N:
    print(ans)
  else:
    print(ans, end=" ")

Submission status: Time Limit Exceeded

Solution code:
# 頂点 v の所属するグループを調べる
def root(v, uni):
  if uni[v] < 0:  # v が親の場合
    return v
  else:           # v が子の場合
    uni[v] = root(uni[v], uni)  # 親のrootを調べる
    return uni[v]

# 頂点 a と頂点 b をつなぐ。もともと同じグループのとき、False を返す
def connect(a, b, uni, sets):
  # まずはそれぞれ根の番号に置き換える
  ra = root(a, uni)
  rb = root(b, uni)
  if ra == rb:  # a と b がそもそも同じグループに属しているなら即終了
    return False
  
  # ra と rb を結合し、rb の親を ra とする
  sets[ra] += sets[rb]
  uni[rb] = ra
  return True


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

road = [0]*(N+1)
rail = [0]*(N+1)

road_sets = [0]*(N+1)
rail_sets = [0]*(N+1)

for i in range(1, N+1):
  road[i] = -i
  rail[i] = -i
  road_sets[i] = [i]
  rail_sets[i] = [i]

for i in range(K):
  a, b = map(int, input().split())
  connect(a, b, road, road_sets)

for i in range(L):
  a, b = map(int, input().split())
  connect(a, b, rail, rail_sets)

for i in range(1, N+1):
  tmp = set(road_sets[root(i, road)]) & set(rail_sets[root(i, rail)])
  ans = len(tmp)
  if i == N:
    print(ans)
  else:
    print(ans, end=" ")

Submission status: Time Limit Exceeded

Solution code:
N,K,L = map(int, raw_input().split())
roads = [0]*K
rails = [0]*L

for i in range(K):
	roads[i] = tuple(map(int, raw_input().split()))

for i in range(L):
	rails[i] = tuple(map(int, raw_input().split()))

road_group = [[i] for i in range(N+1)]
for r in roads:
	for g in road_group:
		if r[0] in g:
			g.append(r[1])
			road_group[r[1]] = g
			break
		if r[1] in g:
			g.append(r[0])
			road_group[r[0]] = g
			break

rail_group = [[i] for i in range(N+1)]
for r in rails:
	for g in rail_group:
		if r[0] in g:
			g.append(r[1])
			rail_group[r[1]] = g
			break
		if r[1] in g:
			g.append(r[0])
			rail_group[r[0]] = g
			break


def func(l1,l2):
	return len([i for i in l1 if i in l2])
anslist = [func(road_group[i], rail_group[i]) for i in range(1,N+1)]
print(' '.join(map(str,anslist)))

Submission status: Time Limit Exceeded

Solution code:
N,K,L = map(int, raw_input().split())
roads = [0]*K
rails = [0]*L

for i in range(K):
	roads[i] = tuple(map(int, raw_input().split()))

for i in range(L):
	rails[i] = tuple(map(int, raw_input().split()))

road_group = [[i] for i in range(N+1)]
for r in roads:
	for g in road_group:
		if r[0] in g:
			g.append(r[1])
			road_group[r[1]] = g
			break
		if r[1] in g:
			g.append(r[0])
			road_group[r[0]] = g
			break

rail_group = [[i] for i in range(N+1)]
for r in rails:
	for g in rail_group:
		if r[0] in g:
			g.append(r[1])
			rail_group[r[1]] = g
			break
		if r[1] in g:
			g.append(r[0])
			rail_group[r[0]] = g
			break

def func(l1,l2):
	s1, s2 = set(l1), set(l2)
	return len(s1.intersection(s2))
anslist = [func(road_group[i], rail_group[i]) for i in range(1,N+1)]
print(' '.join(map(str,anslist)))

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7


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

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    n,k,l = list(map(int, input().split()))
    uk = UnionFind(n)
    ul = UnionFind(n)
    for _ in range(k):
        p,q = list(map(int, input().split()))
        uk.union(p-1,q-1)
    for _ in range(l):
        p,q = list(map(int, input().split()))
        ul.union(p-1,q-1)

    sk = collections.defaultdict(set)
    sl = collections.defaultdict(set)

    for i in range(n):
        sk[uk.find(i)].add(i)
        sl[ul.find(i)].add(i)
    r = []
    for i in range(n):
        r.append(len(sk[uk.find(i)] & sl[ul.find(i)]))

    return " ".join(map(str, r))



print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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


class UnionFind(object):

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

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

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        elif self.rank[x]  < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            self.rank[x] += 1

    def group(self):
        d = defaultdict(set)
        for i in range(self.n):
            d[self.root(i)].add(i)
        return d

load_uf = UnionFind(N)
rail_uf = UnionFind(N)

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

for l in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    rail_uf.unite(r, s)
ld = load_uf.group()
rd = rail_uf.group()

ans = []
d = defaultdict(int)
for i in range(N):
    lp = load_uf.par[i]
    rp = rail_uf.par[i]
    d[lp, rp] += 1
# print(d)

for i in range(N):
    lp = load_uf.par[i]
    rp = rail_uf.par[i]
    if i == N-1:
        print(d[lp, rp])
    else:
        print(d[lp, rp], end=' ')

#     print(rd[rp])
#     print(ld[lp])
#     ans.append(len(ld[lp] & rd[rp]))
# print(str(ans).replace(',', '')[1:-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def add_edge(graph, u, v):
    graph[u].add(v)
    graph[v].add(u)
    return graph

def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

n, k, l = map(int, input().split())
g_road = defaultdict(set)
g_rail = defaultdict(set)
for _ in range(k):
    u, v = map(int, input().split())
    add_edge(g_road, u, v)

for _ in range(l):
    u, v = map(int, input().split())
    add_edge(g_rail, u, v)

#print('#2', g_road)
#print('#2', g_rail)

for i in range(1, n+1):
    print(len(dfs(g_road, i) & dfs(g_rail, i)), end=' ')

Submission status: Time Limit Exceeded

Solution code:
# N K L
# p1 q1
# :
# pK qK
# r1 s1
# :
# rL sL
import numpy as np
N, K, L = map(int, raw_input().split())

# graph
Gp = dict()
Gq = dict()

# conn. components
# p_con_todo = []
# q_con_todo = []
# p_con_list = []
# q_con_list = []

# init
for n in range(1, N+1):
    # p_con_todo.append(str(n))
    # q_con_todo.append(str(n))
    Gp[str(n)] = []
    Gq[str(n)] = []
    
p_con_ids = np.zeros(N, dtype='int')
q_con_ids = np.zeros(N, dtype='int')

# input
for _ in range(K):
    p, q = map(int, raw_input().split())
    Gp[str(p)].append(str(q))
    Gp[str(q)].append(str(p))

for _ in range(L):
    p, q = map(int, raw_input().split())
    Gq[str(p)].append(str(q))
    Gq[str(q)].append(str(p))


    
# DFS
p_con_id = 0
while p_con_ids.min() == 0:
    p_con_id += 1
    ques = [str(p_con_ids.argmin() + 1)]
    while len(ques) > 0:
        n = ques.pop()
        p_con_ids[int(n)-1] = p_con_id
        for m in Gp[n]:
            if p_con_ids[int(m) - 1] == 0:
                ques.append(m)

# DFS
q_con_id = 0
while q_con_ids.min() == 0:
    q_con_id += 1
    ques = [str(q_con_ids.argmin() + 1)]
    while len(ques) > 0:
        n = ques.pop()
        q_con_ids[int(n)-1] = q_con_id
        for m in Gq[n]:
            if q_con_ids[int(m) - 1] == 0:
                ques.append(m)

# print p_con_ids
# print q_con_ids

# count
cnt_g = dict()
for n in range(N):
    ss = str(p_con_ids[n])+' '+str(q_con_ids[n])
    if cnt_g.has_key(ss):
        cnt_g[ss] += 1
    else:
        cnt_g[ss] = 1

# print anser
res_list = []
for n in range(N):
    ss = str(p_con_ids[n])+' '+str(q_con_ids[n])
    res_list.append(str(cnt_g[ss]))
# print res_list
print " ".join(res_list)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, k, l = map(int, raw_input().split())

road = defaultdict(list)
rail = defaultdict(list)
for i in xrange(k):
    pi, qi = map(int, raw_input().split())
    pi -= 1
    qi -= 1
    road[pi].append(qi)
    road[qi].append(pi)

for i in xrange(l):
    si, ri = map(int, raw_input().split())
    si -= 1
    ri -= 1
    rail[si].append(ri)
    rail[ri].append(si)

con1 = [[]] * n
con2 = [[]] * n


def connect(line, con):
    done = [0] * n
    for i in xrange(n):
        if done[i] > 0:
            continue
        to_visit = line[i]
        visited = {i: True}
        j = -1
        while j+1 < len(to_visit):
            j += 1
            place = to_visit[j]
            if visited.get(place):
                continue
            visited[place] = True
            to_visit += line[place]
        svk = set(visited.keys())
        for k, v in visited.iteritems():
            done[k] = 1
            con[k] = svk
        # print con[k]
        # print visited
connect(rail, con1)
connect(road, con2)
# print con1
# print con2
for c1, c2 in zip(con1, con2):
    c = c1 & c2
    print len(c),

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, k, l = map(int, raw_input().split())

road = defaultdict(list)
rail = defaultdict(list)
for i in xrange(k):
    pi, qi = map(int, raw_input().split())
    pi -= 1
    qi -= 1
    road[pi].append(qi)
    road[qi].append(pi)

for i in xrange(l):
    si, ri = map(int, raw_input().split())
    si -= 1
    ri -= 1
    rail[si].append(ri)
    rail[ri].append(si)

con1 = [[]] * n
con2 = [[]] * n


def connect(line, con):
    done = [0] * n
    for i in xrange(n):
        if done[i] > 0:
            continue
        to_visit = line[i]
        visited = {i: True}
        j = -1
        while j+1 < len(to_visit):
            j += 1
            place = to_visit[j]
            if visited.get(place):
                continue
            visited[place] = True
            to_visit += line[place]
        for k, v in visited.iteritems():
            done[k] = 1
            con[k] = visited.keys()
        # print con[k]
        # print visited
connect(rail, con1)
connect(road, con2)
# print con1
# print con2
for c1, c2 in zip(con1, con2):
    c = set(c1) & set(c2)
    print len(c),

Submission status: Time Limit Exceeded

Solution code:
# N K L
# p1 q1
# :
# pK qK
# r1 s1
# :
# rL sL
import numpy as np
N, K, L = map(int, raw_input().split())

# graph
Gp = dict()
Gq = dict()

# conn. components
p_con_todo = []
q_con_todo = []
p_con_list = []
q_con_list = []

# init
for n in range(1, N+1):
    p_con_todo.append(str(n))
    q_con_todo.append(str(n))
    Gp[str(n)] = []
    Gq[str(n)] = []
    
p_con_ids = np.zeros(N, dtype='int')
q_con_ids = np.zeros(N, dtype='int')

# input
for _ in range(K):
    p, q = map(int, raw_input().split())
    Gp[str(p)].append(str(q))
    Gp[str(q)].append(str(p))

for _ in range(L):
    p, q = map(int, raw_input().split())
    Gq[str(p)].append(str(q))
    Gq[str(q)].append(str(p))


    
# DFS
p_con_id = 0
while len(p_con_todo) > 0:
    p_con_id += 1
    ques = [p_con_todo[0]]
    conn = []
    while len(ques) > 0:
        n = ques.pop()
        conn.append(n)
        p_con_ids[int(n)-1] = p_con_id
        for m in Gp[n]:
            if m in conn:
                pass
            else:
                ques.append(m)
    p_con_todo = list(set(p_con_todo) - set(conn))
    p_con_list.append(conn)

# DFS
q_con_id = 0
while len(q_con_todo) > 0:
    q_con_id += 1
    ques = [q_con_todo[0]]
    conn = []
    while len(ques) > 0:
        n = ques.pop()
        conn.append(n)
        q_con_ids[int(n)-1] = q_con_id
        for m in Gq[n]:
            if m in conn:
                pass
            else:
                ques.append(m)
    q_con_todo = list(set(q_con_todo) - set(conn))
    q_con_list.append(conn)

# print p_con_ids
# print q_con_ids

# print anser
res_list = []
for n in range(N):
    res = int((np.ones(N)[(p_con_ids == p_con_ids[n]) * (q_con_ids == q_con_ids[n])]).sum())
    res_list.append(str(res))
# print res_list
print " ".join(res_list)

Submission status: Time Limit Exceeded

Solution code:
n, k, l = map(int, raw_input().split())
roads = []
for i in range(k):
    p, q = map(int, raw_input().split())
    if roads == []:
        roads.append([p,q])
    else:
        for j in roads:
            if p in j:
                if not q in j:
                    j.append(q)
            elif q in j:
                j.append(p)
            else:
                roads.append([p, q])
rails = []
for i in range(l):
    r, s = map(int, raw_input().split())
    if rails == []:
        rails.append([r,s])
    else:
        for j in rails:
            if r in j:
                if not s in j:
                    j.append(s)
            elif s in j:
                j.append(r)
            else:
                rails.append([r, s])
roads.sort()
rails.sort()
# print roads
# print rails
a = [1] * n
for i in range(1, n+1):
    for road in roads:
        if road[0] > i:
            break
        elif i in road:
            for rail in rails:
                if rail[0] > i:
                    break
                elif i in rail:
                    # print [x for x in road if x in rail]
                    a[i-1] = len([x for x in road if x in rail])
                    break
a = map(str, a)
print ' '.join(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, k, l = map(int, raw_input().split())

road = defaultdict(list)
rail = defaultdict(list)
for i in xrange(k):
    pi, qi = map(int, raw_input().split())
    pi -= 1
    qi -= 1
    road[pi].append(qi)
    road[qi].append(pi)

for i in xrange(l):
    si, ri = map(int, raw_input().split())
    si -= 1
    ri -= 1
    rail[si].append(ri)
    rail[ri].append(si)

con1 = [[]] * n
con2 = [[]] * n


def connect(line, con):
    done = [0] * n
    for i in xrange(n):
        if done[i] > 0:
            continue
        can_visit = set(line[i])
        can_visit.add(i)
        to_visit = line[i]
        visited = {i: True}
        j = -1
        while j+1 < len(to_visit):
            j += 1
            place = to_visit[j]
            if visited.get(place):
                continue
            visited[place] = True
            can_visit |= set(line[place])
            to_visit += line[place]
        for k, v in visited.iteritems():
            done[k] = 1
            con[k] = can_visit
        # print can_visit
connect(rail, con1)
connect(road, con2)

for c1, c2 in zip(con1, con2):
    c = c1 & c2
    print len(c),

Submission status: Time Limit Exceeded

Solution code:
class UF():
    def __init__(self, n):
        self.root = [i for i in range(n)]
    def findRoot(self, a):
        r = self.root[a]
        if r == a:
            return r
        else:
            r = self.findRoot(r)
            self.root[a] = r
            return r
    def connect(self, a, b):
        self.root[self.findRoot(a)] = self.findRoot(b)
    def isConnected(self, a, b):
        return self.findRoot(a) == self.findRoot(b)

N, K, L = list(map(int, input().split()))
road, rail = UF(N), UF(N)

for i in range(K):
    a, b = input().split()
    a, b = int(a) - 1, int(b) - 1
    road.connect(a, b)

for i in range(L):
    a, b = input().split()
    a, b = int(a) - 1, int(b) - 1
    rail.connect(a, b)

o = [0] * N
for i in range(N):
    for j in range(i, N):
        if road.isConnected(i, j) and rail.isConnected(i, j):
            o[i] += 1
            if not i == j:
                o[j] += 1

for i in range(N):
    print(o[i], end=' ')

Submission status: Time Limit Exceeded

Solution code:
# N K L
# p1 q1
# :
# pK qK
# r1 s1
# :
# rL sL
import numpy as np
N, K, L = map(int, raw_input().split())

# graph
Gp = dict()
Gq = dict()

# conn. components
p_con_todo = []
q_con_todo = []

# init
for n in range(1, N+1):
    p_con_todo.append(str(n))
    q_con_todo.append(str(n))
    Gp[str(n)] = []
    Gq[str(n)] = []
    
p_con_ids = np.zeros(N, dtype='int')
q_con_ids = np.zeros(N, dtype='int')

# input
for _ in range(K):
    p, q = map(int, raw_input().split())
    Gp[str(p)].append(str(q))
    Gp[str(q)].append(str(p))

for _ in range(L):
    p, q = map(int, raw_input().split())
    Gq[str(p)].append(str(q))
    Gq[str(q)].append(str(p))


    
# DFS
p_con_id = 0
while len(p_con_todo) > 0:
    p_con_id += 1
    ques = [p_con_todo[0]]
    conn = []
    while len(ques) > 0:
        n = ques.pop()
        conn.append(n)
        p_con_ids[int(n)-1] = p_con_id
        for m in Gp[n]:
            if m in conn:
                pass
            else:
                ques.append(m)
    p_con_todo = [n for n in p_con_todo if n not in conn]

# DFS
q_con_id = 0
while len(q_con_todo) > 0:
    q_con_id += 1
    ques = [q_con_todo[0]]
    conn = []
    while len(ques) > 0:
        n = ques.pop()
        conn.append(n)
        q_con_ids[int(n)-1] = q_con_id
        for m in Gq[n]:
            if m in conn:
                pass
            else:
                ques.append(m)
    q_con_todo = [n for n in q_con_todo if n not in conn]

# print p_con_ids
# print q_con_ids

# print anser
res_list = []
for n in range(N):
    res = int((np.ones(N)[(p_con_ids == p_con_ids[n]) * (q_con_ids == q_con_ids[n])]).sum())
    res_list.append(str(res))
# print res_list
print " ".join(res_list)

Submission status: Time Limit Exceeded

Solution code:
class UF():
    def __init__(self, n):
        self.root = [i for i in range(n)]
    def findRoot(self, a):
        r = self.root[a]
        if r == a:
            return r
        else:
            r = self.findRoot(r)
            self.root[a] = r
            return r
    def connect(self, a, b):
        self.root[self.findRoot(a)] = self.findRoot(b)
    def isConnected(self, a, b):
        return self.findRoot(a) == self.findRoot(b)

N, K, L = list(map(int, input().split()))
road, rail = UF(N), UF(N)

for i in range(K):
    a, b = input().split()
    a, b = int(a) - 1, int(b) - 1
    road.connect(a, b)

for i in range(L):
    a, b = input().split()
    a, b = int(a) - 1, int(b) - 1
    rail.connect(a, b)

for i in range(N):
    c = 0
    for j in range(N):
        if road.isConnected(i, j) and rail.isConnected(i, j):
            c += 1
    print(c, end=' ')

Submission status: Time Limit Exceeded

Solution code:
import collections

class UnionFind:
    def __init__(self, n):
        self._id = list(range(n))
        self._sz = [1] * n

    def _root(self, i):
        j = i
        while (j != self._id[j]):
            self._id[j] = self._id[self._id[j]]
            j = self._id[j]
        return j

    def find(self, p, q):
        return self._root(p) == self._root(q)

    def union(self, p, q):
        i = self._root(p)
        j = self._root(q)
        if (self._sz[i] < self._sz[j]):
            self._id[i] = j
            self._sz[j] += self._sz[i]
        else:
            self._id[j] = i
            self._sz[i] += self._sz[j]

n, k, l = [int(x) for x in input().split()]
pqs = set(tuple(int(x) - 1 for x in input().split()) for _ in range(k))
rss = set(tuple(int(x) - 1 for x in input().split()) for _ in range(l))

road = UnionFind(n)
for pq in pqs:
    road.union(*pq)

rail = UnionFind(n)
for rs in rss:
    rail.union(*rs)

roadset = collections.defaultdict(set)
railset = collections.defaultdict(set)
for i in range(n):
    roadset[road._root(i)].add(i)
    railset[rail._root(i)].add(i)

print(' '.join([str(len(roadset[road._root(i)] & railset[rail._root(i)])) for i in range(n)]))

Submission status: Time Limit Exceeded

Solution code:
# N K L
# p1 q1
# :
# pK qK
# r1 s1
# :
# rL sL
import numpy as np
N, K, L = map(int, raw_input().split())

# graph
Gp = dict()
Gq = dict()

# conn. components
p_con_todo = []
q_con_todo = []

# init
for n in range(1, N+1):
    p_con_todo.append(str(n))
    q_con_todo.append(str(n))
    Gp[str(n)] = []
    Gq[str(n)] = []
    
p_con_ids = np.zeros(N, dtype='int')
q_con_ids = np.zeros(N, dtype='int')

# input
for _ in range(K):
    p, q = map(int, raw_input().split())
    Gp[str(p)].append(str(q))
    Gp[str(q)].append(str(p))

for _ in range(L):
    p, q = map(int, raw_input().split())
    Gq[str(p)].append(str(q))
    Gq[str(q)].append(str(p))


    
# DFS
p_con_id = 0
while len(p_con_todo) > 0:
    p_con_id += 1
    ques = [p_con_todo[0]]
    conn = []
    while len(ques) > 0:
        n = ques.pop()
        conn.append(n)
        p_con_ids[int(n)-1] = p_con_id
        for m in Gp[n]:
            if m in conn:
                pass
            else:
                ques.append(m)
    p_con_todo = [n for n in p_con_todo if n not in conn]

# DFS
q_con_id = 0
while len(q_con_todo) > 0:
    q_con_id += 1
    ques = [q_con_todo[0]]
    conn = []
    while len(ques) > 0:
        n = ques.pop()
        conn.append(n)
        q_con_ids[int(n)-1] = q_con_id
        for m in Gq[n]:
            if m in conn:
                pass
            else:
                ques.append(m)
    q_con_todo = [n for n in q_con_todo if n not in conn]

# print p_con_ids
# print q_con_ids

# print anser
res_list = []
for n in range(N):
    res = len([i for i in range(N) if p_con_ids[i] == p_con_ids[n] and q_con_ids[i] == q_con_ids[n]])
    res_list.append(str(res))
# print res_list
print " ".join(res_list)

Submission status: Time Limit Exceeded

Solution code:
# マージO(n)かかっちゃう
class union_find(object):
 	"""union-find tree"""
 	def __init__(self, length):
 		self.length = length
 		self.unionnumber=0
 		self.unionlist=[[]]
 		self.num=list(-1 for i in range(length))

 	def unite(self,i,j):
 		if self.num[i]==-1:
 			if self.num[j]==-1:
 				self.unionlist[self.unionnumber].extend([i,j])
 				self.num[i]=self.unionnumber
 				self.num[j]=self.unionnumber
 				self.unionnumber+=1
 				self.unionlist.append([])
 			else:
 				tmp=i 
 				i=j 
 				j=tmp 
 		if self.num[i]!=-1:
 			if self.num[j]!=-1:
 				if self.num[i]==self.num[j]:
 					pass
 				else:
 					self.unionlist[self.num[i]].extend(self.unionlist[self.num[j]])
 					tmp=self.num[j]
 					for k in self.unionlist[self.num[j]]:
 						self.num[k]=self.num[i]
 					self.unionlist[tmp]="del"
 			else:
 				self.num[j]=self.num[i]
 				self.unionlist[self.num[i]].append(j)

 	def same(self,i,j):
 		if self.num[i]==-1 or self.num[j]==-1:
 			return(False)
 		else:
 			return(self.num[i]==self.num[j])


N,K,L=list(map(int,input().split()))
road=union_find(N)
rail=union_find(N)

for i in range(K):
	a=list(map(int,input().split()))
	road.unite(a[0]-1,a[1]-1)

for i in range(L):
	a=list(map(int,input().split()))
	rail.unite(a[0]-1,a[1]-1)

res=[0 for i in range(N)]
for i in range(N):
	if res[i]==0:
		n=road.num[i]
		A=road.unionlist[n]
		m=rail.num[i]
		B=set(rail.unionlist[m]).intersection(A)
		l=len(B)
		if l==0:
			B=[i]
			l=1
		for j in B:
			res[j]=l

for i in res:
	print(i,end=" ")
print("")