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:
N,K,L = map(int,input().split())
roads = [list(map(int,input().split())) for _ in range(K)]
rails = [list(map(int,input().split())) for _ in range(L)]
outputs = [1 for _ in range(N)]

class UF():
  def __init__(self,size):
    self.table = [-1 for _ in range(size)]
    self.results = {}
    
  def find(self,x):
    target = x
    while self.table[x] >= 0:
      x = self.table[x]
    if 0 < self.table[target]:
      self.table[target] = x
    return 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[s2] = s1
        if s2 in self.results:
          self.results[s1] = (self.results[s1] | self.results[s2])
          self.results.pop(s2)
        else:
          self.results[s1].add(s2)
      else:
        self.table[s1] = s2
        self.table[s2] -= 1
        if s1 in self.results and s2 in self.results:
          self.results[s2] = self.results[s1] | self.results[s2]
          self.results.pop(s1)
        elif s2 in self.results:
          self.results[s2].add(s1)
        else:
          self.results[s2] = set([s1,s2])
    return

w = UF(N+1)

for r in roads:
  w.union(r[0],r[1])

t = UF(N+1)
for l in rails:
  t.union(l[0],l[1])

for x in range(1,N+1):
  X= w.find(x)
  Y = t.find(x)
  if X in w.results and Y in t.results:
    outputs[x-1] = len(w.results[X] & t.results[Y])
  else:
    outputs[x-1] = 1
print(' '.join(map(str,outputs)))

Submission status: Time Limit Exceeded

Solution code:
N,K,L = map(int,input().split())
roads = [list(map(int,input().split())) for _ in range(K)]
rails = [list(map(int,input().split())) for _ in range(L)]
outputs = [1 for _ in range(N)]

class UF():
  def __init__(self,size):
    self.table = [-1 for _ in range(size)]
    self.results = {}
    
  def find(self,x):
    target = x
    while self.table[x] >= 0:
      x = self.table[x]
    if 0 < self.table[target] and self.table[target] != x:
      self.table[target] = x
    return 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[s2] = s1
        if s2 in self.results:
          self.results[s1] = (self.results[s1] | self.results[s2])
          self.results.pop(s2)
        else:
          self.results[s1].add(s2)
      else:
        self.table[s1] = s2
        self.table[s2] -= 1
        if s1 in self.results and s2 in self.results:
          self.results[s2] = self.results[s1] | self.results[s2]
          self.results.pop(s1)
        elif s2 in self.results:
          self.results[s2].add(s1)
        else:
          self.results[s2] = set([s1,s2])
    return

w = UF(N+1)

for r in roads:
  w.union(r[0],r[1])

t = UF(N+1)
for l in rails:
  t.union(l[0],l[1])

for x in range(1,N+1):
  if w.find(x) in w.results and t.find(x) in t.results:
    outputs[x-1] = len(w.results[w.find(x)] & t.results[t.find(x)])
  else:
    outputs[x-1] = 1
print(' '.join(map(str,outputs)))

Submission status: Time Limit Exceeded

Solution code:
N,K,L = map(int,input().split())
roads = [list(map(int,input().split())) for _ in range(K)]
rails = [list(map(int,input().split())) for _ in range(L)]
outputs = [1 for _ in range(N)]

class UF():
  def __init__(self,size):
    self.table = [-1 for _ in range(size)]
    
  def find(self,x):
    target = x
    while self.table[x] >= 0:
      x = self.table[x]
    if 0 < self.table[target] and self.table[target] != x:
      self.table[target] = x
    return x
  
  def union(self,x,y):
    s1 = self.find(x)
    s2 = self.find(y)
    if s1 < s2:
      self.table[s2] = s1
    elif s2 < s1:
      self.table[s1] = s2
    elif s1 < 0 and s2 < 0:
      self.table[s2] = s1
      self.table[s1] += -1
    return
  
  def init_group(self):
    cands = []
    for i in range(1,len(self.table)):
      if self.table[i] < 0:
        cands.append(i)
    self.results={}
    for c in cands:
      self.results[c] = set([c])
    for j in range(1,len(self.table)):
      self.results[self.find(j)].add(j)
    return
    
w = UF(N+1)

for r in roads:
  w.union(r[0],r[1])
w.init_group()

t = UF(N+1)
for l in rails:
  t.union(l[0],l[1])
t.init_group()
for x in range(1,N+1):
  outputs[x-1] = len(w.results[w.find(x)] & t.results[t.find(x)])
print(' '.join(map(str,outputs)))

Submission status: Time Limit Exceeded

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

gK=[set([x]) for x in range(N)]
gL=[set([x]) for x in range(N)]

class UnionFind(object):
  def __init__(self,n):
    self.table=[-1]*n
 
  def find(self,x):
    parent=self.table[x]
    if parent<0:
      return x
    else:
      root=self.find(parent)
      self.table[x]=root
      return root
 
  def union(self,a,b,li):
    root1=self.find(a)
    root2=self.find(b)
    if root1 != root2:
      if self.table[root1] != self.table[root2]:
        if self.table[root1] < self.table[root2]:
          self.table[root2]=root1
          li[root1]=(li[root1] | li[root2])
        else:
          self.table[root1]=root2
          li[root2]=(li[root1] | li[root2])
      else:
        self.table[root1]+=(-1)
        self.table[root2]=root1
        li[root1]=(li[root1] | li[root2])
      
ufK=UnionFind(N)
for i in range(K):
  p,q=map(int,input().split())
  gK[p-1].add(q-1)
  gK[q-1].add(p-1)
  ufK.union(p-1,q-1,gK)

ufL=UnionFind(N)
for i in range(L):
  p,q=map(int,input().split())
  gL[p-1].add(q-1)
  gL[q-1].add(p-1)
  ufL.union(p-1,q-1,gL)

ans=[]
for i in range(N):
  a=ufK.find(i)
  b=ufL.find(i)
  ab= (gK[a] & gL[b])
  ans.append(len(ab))

print(*ans)

Submission status: Time Limit Exceeded

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


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.group = [set([i]) for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            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
            gx = list(self.group[x])
            gy = list(self.group[y])
            gx.extend(gy)
            gy.extend(gx)
            self.group[x] = set(gx)
            self.group[y] = set(gy)
        else:
            self.par[y] = x
            gx = list(self.group[x])
            gy = list(self.group[y])
            gx.extend(gy)
            gy.extend(gx)
            self.group[x] = set(gx)
            self.group[y] = set(gy)
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


road_uf = UnionFind(N)
train_uf = UnionFind(N)

for p, q in roads:
    road_uf.union(p, q)

for r, s in trains:
    train_uf.union(r, s)

road_link = road_uf.group
road_par = road_uf.par
train_link = train_uf.group
train_par = train_uf.par

for i in range(1, N+1):
    road_link[i] = road_link[road_par[i]]
    train_link[i] = train_link[train_par[i]]

ans = []
for n in range(1, N+1):
    ans.append(str(len(road_link[n] & train_link[n])))

print(" ".join(ans))

Submission status: Time Limit Exceeded

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


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.group = [set([i]) for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            self.group[x].add(self.par[x])
            gx = list(self.group[x])
            gp = list(self.group[self.par[x]])
            gx.extend(gp)
            gp.extend(gx)
            self.group[x] = set(gx)
            self.group[self.par[x]] = set(gp)
            return x
        else:
            self.par[x] = self.find(self.par[x])
            gx = list(self.group[x])
            gp = list(self.group[self.par[x]])
            gx.extend(gp)
            gp.extend(gx)
            self.group[x] = set(gx)
            self.group[self.par[x]] = set(gp)
            return self.par[x]

    # 併合
    def union(self, x, y):
        self.group[y].add(x)
        self.group[x].add(y)
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            gx = list(self.group[x])
            gy = list(self.group[y])
            gx.extend(gy)
            gy.extend(gx)
            self.group[x] = set(gx)
            self.group[y] = set(gy)
        else:
            self.par[y] = x
            gx = list(self.group[x])
            gy = list(self.group[y])
            gx.extend(gy)
            gy.extend(gx)
            self.group[x] = set(gx)
            self.group[y] = set(gy)
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


road_uf = UnionFind(N)
train_uf = UnionFind(N)

for p, q in roads:
    road_uf.union(p, q)

for r, s in trains:
    train_uf.union(r, s)

road_link = road_uf.group
train_link = train_uf.group

for i in range(1, N+1):
    road_link[i] = road_link[road_uf.par[i]]
    train_link[i] = train_link[train_uf.par[i]]

ans = []
for n in range(1, N+1):
    ans.append(str(len(road_link[n] & train_link[n])))

print(" ".join(ans))

Submission status: Time Limit Exceeded

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


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)


road_uf = UnionFind(N)
train_uf = UnionFind(N)

for p, q in roads:
    road_uf.union(p, q)
for r, s in trains:
    train_uf.union(r, s)

road_link = road_uf.par
train_link = train_uf.par

ans = []
for n in range(1, N+1):
    road_set = set()
    train_set = set()
    for i in range(1, N+1):
        if road_link[i] == road_link[n]:
            road_set.add(i)
        if train_link[i] == train_link[n]:
            train_set.add(i)
    ans.append(str(len(road_set & train_set)))

print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict
N,K,L=map(int, raw_input().split())

nl=[ [] for i in range(N+1) ]

c1=set()

for i in range(K):
	p,q=map(int, raw_input().split())
	nl[p].append(q)
	nl[q].append(p)
	c1.add(p)
	c1.add(q)

nl2=[ [] for i in range(N+1) ]
c2=set()

for i in range(L):
	p,q=map(int, raw_input().split())
	nl2[p].append(q)
	nl2[q].append(p)
	c2.add(p)
	c2.add(q)


road=[ None for i in range(N+1) ]
railway=[ None for i in range(N+1) ]
l1=defaultdict(lambda: [])
l2=defaultdict(lambda: [])

def bfs(start,nl,type):
	V=[ None for i in range(N+1)]
	q = deque([]) 
	V[start]=1
	tmp=[]
	tmp.append(start)

	if type=="road": road[start]=start
	elif type=="railway": railway[start]=start

	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in nl[v]:
			if V[i] is None:
				V[i]=1
				q.append(i)
				tmp.append(i)
				if type=="road": road[i]=start
				elif type=="railway": railway[i]=start

	if type=="road": l1[start]=tmp
	elif type=="railway": l2[start]=tmp				
	return V




for i in c1:
	if road[i] is None: bfs(i,nl,"road")


for i in c2:
	if railway[i] is None: bfs(i,nl2,"railway")



for idx,i in enumerate( zip(road,railway) ):
	x=i[0]; y=i[1]
	if idx==0: continue
	if (x and y) is None:
		print 1,
	else:
		print len( set(l1[x]) & set(l2[y]) ),

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict
N,K,L=map(int, raw_input().split())

nl=[ [] for i in range(N+1) ]

c1=set()

for i in range(K):
	p,q=map(int, raw_input().split())
	nl[p].append(q)
	nl[q].append(p)
	c1.add(p)
	c1.add(q)

nl2=[ [] for i in range(N+1) ]
c2=set()

for i in range(L):
	p,q=map(int, raw_input().split())
	nl2[p].append(q)
	nl2[q].append(p)
	c2.add(p)
	c2.add(q)


road=[ None for i in range(N+1) ]
railway=[ None for i in range(N+1) ]

def bfs(start,nl,type):
	V=[ None for i in range(N+1)]
	q = deque([]) 
	V[start]=1
	if type=="road": road[start]=start
	elif type=="railway": railway[start]=start

	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in nl[v]:
			if V[i] is None:
				V[i]=1
				q.append(i)
				if type=="road": road[i]=start
				elif type=="railway": railway[i]=start					
	return V




for i in c1:
	if road[i] is None: bfs(i,nl,"road")


for i in c2:
	if railway[i] is None: bfs(i,nl2,"railway")



l1=defaultdict(lambda: [])
for i in range(1,N+1):
	if road[i] is not None:
		l1[road[i]].append(i)


l2=defaultdict(lambda: [])
for i in range(1,N+1):
	if railway[i] is not None:
		l2[railway[i]].append(i)


for idx,i in enumerate( zip(road,railway) ):
	x=i[0]; y=i[1]
	if idx==0: continue
	if (x and y) is None:
		print 1,
	else:
		print len( set(l1[x]) & set(l2[y]) ),

Submission status: Time Limit Exceeded

Solution code:
N, K, L = map(int, input().split())
u1, u2 = list(range(N+1)), list(range(N+1))

def root(u, r):
    if u[r] == r:
        return r
    u[r] = root(u, u[r])
    return u[r]

def update(u, r, n):
    u[root(u, n)] = root(u, r)

for i in range(K):
    p, q = map(int, input().split())
    update(u1, p, q)

for i in range(L):
    r, s = map(int, input().split())
    update(u2, r, s)

c = {}
rs = [(root(u1, i), root(u2, i)) for i in range(1, N+1)]
for r in rs:
    if r in c:
        c[r] += 1
    else:
        c[r] = 1
 
print(' '.join(map(str, [c[r] for r in rs])))

Submission status: Time Limit Exceeded

Solution code:
class Node():
	def __init__(self, value):
		self.value = value
		self.connect = []
		self.visited = False

	def getConnect(self):
		return self.connect

	def getConnectValues(self):
		res = []
		for node in self.connect:
			res.append(node.getValue())
		return res

	def getValue(self):
		return self.value

	def addConnect(self, connectNode):
		self.connect.append(connectNode)

	def isConnected(self, node):
		self.visited = True
		if node in self.connect:
			return True
		for i in range(len(self.connect)):
			if self.connect[i].visited:
				continue
			elif self.connect[i].isConnected(node):
				return True
		return False

def refreshVisited(list1):
	for i in range(1,len(list1)):
		list1[i].visited = False

line1 = input()
line1 = line1.split(" ")
numCities = int(line1[0])
numRoads = int(line1[1])
numRails = int(line1[2])

road = [0]
rail = [0]
res = [0]

for i in range(1, numCities+1):
	road.append(Node(i))
	rail.append(Node(i))
	res.append(1)

for i in range(numRoads):
	lineI = input().split(" ")
	city1 = road[int(lineI[0])]
	city2 = road[int(lineI[1])]
	city1.addConnect(city2)
	city2.addConnect(city1)

for i in range(numRails):
	lineI = input().split(" ")
	city1 = rail[int(lineI[0])]
	city2 = rail[int(lineI[1])]
	city1.addConnect(city2)
	city2.addConnect(city1)

for i in range(1, numCities+1):
	for j in range(i+1,numCities+1):
		if road[i].isConnected(road[j]) and rail[i].isConnected(rail[j]):
			res[i] += 1
			res[j] += 1
		refreshVisited(rail)
		refreshVisited(road)

res = res[1:]

for i in range(0,len(res)-1):
	print(res[i], end=" ")
print(res[len(res)-1])

Submission status: Time Limit Exceeded

Solution code:
n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[[i] for i in range(n)]
rail=[[i] for i in range(n)]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].append(q)
    road[q].append(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].append(s)
    rail[s].append(r)
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(road[tmp])
        road[i].extend(road[tmp])
    for j in road[i]:
        road[j]=road[i]
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(rail[tmp])
        rail[i].extend(rail[tmp])
    for j in rail[i]:
        rail[j]=rail[i]
ans=[0]*n
for i in range(n):
    if ans[i]!=0:
        continue
    sumset=set(road[i])&set(rail[i])
    for j in sumset:
        ans[j]=str(len(sumset))
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[[i] for i in range(n)]
rail=[[i] for i in range(n)]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].append(q)
    road[q].append(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].append(s)
    rail[s].append(r)
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(road[tmp])
        road[i].extend(road[tmp])
    for j in road[i]:
        road[j]=road[i]
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(rail[tmp])
        rail[i].extend(rail[tmp])
    for j in rail[i]:
        rail[j]=rail[i]
ans=[]
for i,j in zip(road,rail):
    ans.append(str(len(set(i)&set(j))))
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[[i] for i in range(n)]
rail=[[i] for i in range(n)]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].append(q)
    road[q].append(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].append(s)
    rail[s].append(r)
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(road[tmp])
        road[i].extend(road[tmp])
    for j in road[i]:
        road[j]=road[i]
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(rail[tmp])
        rail[i].extend(rail[tmp])
    for j in rail[i]:
        rail[j]=rail[i]
ans=[]
for i,j in zip(road,rail):
    ans.append(str(len(set(i)&set(j))))
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[[i] for i in range(n)]
rail=[[i] for i in range(n)]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].append(q)
    road[q].append(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].append(s)
    rail[s].append(r)
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(road[tmp])
        road[i].extend(road[tmp])
    for j in road[i]:
        road[j]=road[i]
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        d.extend(rail[tmp])
        rail[i].extend(rail[tmp])
    for j in rail[i]:
        rail[j]=rail[i]
ans=[]
for i,j in zip(road,rail):
    ans.append(str(len(set(i)&set(j))))
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[[i] for i in range(n)]
rail=[[i] for i in range(n)]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].append(q)
    road[q].append(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].append(s)
    rail[s].append(r)
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        for j in road[tmp]:
            if j not in road[i]:
                d.append(j)
                road[i].append(j)
    for j in road[i]:
        road[j]=road[i]
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        for j in rail[tmp]:
            if j not in rail[i] :
                d.append(j)
                rail[i].append(j)
    for j in rail[i]:
        rail[j]=rail[i]
ans=[]
for i,j in zip(road,rail):
    ans.append(str(len(set(i)&set(j))))
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[[] for i in [0]*n]
rail=[[] for i in [0]*n]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].append(q)
    road[q].append(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].append(s)
    rail[s].append(r)
for i in range(n):
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        for j in road[tmp]:
            if j not in road[i]:
                d.append(j)
                road[i].append(j)
for i in range(n):
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        for j in rail[tmp]:
            if j not in rail[i] and j!=i:
                d.append(j)
                rail[i].append(j)
ans=[]
for i,j in zip(road,rail):
    ans.append(str(len(set(i)&set(j))+1))
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 1)

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size + 1))

    def is_same_set(self, x: int, y: int) -> bool:
        return self.find_root(x) == self.find_root(y)

    def union_set(self, x: int, y: int):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return

        self.parent[x] = y

    def find_root(self, x: int):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find_root(self.parent[x])
            return self.parent[x]


def dfs(n, used, edges, uf: UnionFind):
    used[n] = True
    for a in edges[n]:
        if not used[a]:
            uf.union_set(n, a)
            dfs(a, used, edges, uf)


def main():
    N, K, L = map(int, input().split())
    d1 = defaultdict(list)
    for _ in range(K):
        p, q = map(int, input().split())
        p -= 1
        q -= 1
        d1[p].append(q)
        d1[q].append(p)

    d2 = defaultdict(list)
    for _ in range(L):
        r, s = map(int, input().split())
        r -= 1
        s -= 1
        d2[r].append(s)
        d2[s].append(r)

    uf1 = UnionFind(N)
    used1 = [False] * N
    for n in range(N):
        if not used1[n]:
            dfs(n, used1, d1, uf1)

    uf2 = UnionFind(N)
    used2 = [False] * N
    for n in range(N):
        if not used2[n]:
            dfs(n, used2, d2, uf2)

    used3 = [False] * N
    ans = [0] * N
    for n1 in range(N):
        if used3[n1]:
            continue
        num = 1
        l = [n1]
        for n2 in range(n1 + 1, N):
            if not used3[n2]:
                if uf1.is_same_set(n1, n2) and uf2.is_same_set(n1, n2):
                    used3[n2] = True
                    l.append(n2)
                    num += 1
        for n in l:
            ans[n] = num

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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)]
dict_load={i+1:i+1 for i in range(N)}
dict_rail={i+1:i+1 for i in range(N)}

for i in range(K):
  if dict_load[pq[i][0]]!=dict_load[pq[i][1]]:
    for j in range(N):
      if dict_load[j+1]==max(dict_load[pq[i][0]],dict_load[pq[i][1]]):
        dict_load[j+1]=min(dict_load[pq[i][0]],dict_load[pq[i][1]])
for i in range(L):
  if dict_rail[rs[i][0]]!=dict_rail[rs[i][1]]:
    for j in range(N):
      if dict_rail[j+1]==max(dict_rail[rs[i][0]],dict_rail[rs[i][1]]):
        dict_rail[j+1]=min(dict_rail[rs[i][0]],dict_rail[rs[i][1]])

group=[[dict_load[j+1],dict_rail[j+1]] for j in range(N)]
dict_load_rail={}
for j in range(N):
  if (dict_load[j+1],dict_rail[j+1]) in dict_load_rail:
    dict_load_rail[(dict_load[j+1],dict_rail[j+1])]+=1
  else:
    dict_load_rail[(dict_load[j+1],dict_rail[j+1])]=1
for j in range(N):
  print(dict_load_rail[(dict_load[j+1],dict_rail[j+1])])

Submission status: Time Limit Exceeded

Solution code:
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)]
dict_load={i+1:i+1 for i in range(N)}
dict_rail={i+1:i+1 for i in range(N)}

for i in range(K):
  if dict_load[pq[i][0]]!=dict_load[pq[i][1]]:
    for j in range(N):
      if dict_load[j+1]==max(dict_load[pq[i][0]],dict_load[pq[i][1]]):
        dict_load[j+1]=min(dict_load[pq[i][0]],dict_load[pq[i][1]])
for i in range(L):
  if dict_rail[rs[i][0]]!=dict_rail[rs[i][1]]:
    for j in range(N):
      if dict_rail[j+1]==max(dict_rail[rs[i][0]],dict_rail[rs[i][1]]):
        dict_rail[j+1]=min(dict_rail[rs[i][0]],dict_rail[rs[i][1]])

group=[[dict_load[j+1],dict_rail[j+1]] for j in range(N)]
for j in range(N):
  print(group.count([dict_load[j+1],dict_rail[j+1]]))

Submission status: Time Limit Exceeded

Solution code:
class Sets:
  def __init__(self):
    self.sets = []
  def get_group(self, a):
    if a < 0: return -1
    for i in range(len(self.sets)):
      if a in self.sets[i]:
        return i
    return -1
  def add_same_pair(self, a, b):
    ga = self.get_group(a)
    gb = self.get_group(b)
    if ga < 0 and gb < 0:
      self.sets.append(set([a,b]))
    elif ga == gb:
      return
    elif ga >= 0 and gb < 0:
      self.sets[ga].add(b)
    elif ga < 0 and gb >= 0:
      self.sets[gb].add(a)
    else:
      gmin = min(ga,gb)
      gmax = max(ga,gb)
      s = self.sets.pop(gmax)
      self.sets[gmin] = self.sets[gmin].union(s)
  def get_setids(self, n):
    setids = [-1 for i in range(n)]
    for setid in range(len(self.sets)):
      for e in self.sets[setid]:
        setids[e] = setid
    return setids
  def __str__(self):
    return str(self.sets)

N,K,L = map(int, raw_input().split())
roads = [-1 for i in range(N)]
rails = [-1 for i in range(N)]
road_sets = Sets()
rail_sets = Sets()

for i in range(K):
  p,q = map(int, raw_input().split())
  p -= 1
  q -= 1
  road_sets.add_same_pair(p,q)

for i in range(L):
  r,s = map(int, raw_input().split())
  r -= 1
  s -= 1
  rail_sets.add_same_pair(r,s)

road_ids = road_sets.get_setids(N)
rail_ids = rail_sets.get_setids(N)
result = [1 for i in range(N)]
combi_counts = {}
for i in range(N):
  road = road_ids[i]
  rail = rail_ids[i]
  if road < 0 or rail < 0:
    continue
  if (road,rail) in combi_counts:
    combi_counts[(road,rail)] += 1
  else:
    combi_counts[(road,rail)] = 1

for i in range(N):
  road = road_ids[i]
  rail = rail_ids[i]
  if road < 0 or rail < 0:
    continue
  result[i] = combi_counts[(road,rail)]
print ' '.join(map(str, result))

Submission status: Time Limit Exceeded

Solution code:
class Sets:
  def __init__(self):
    self.sets = []
  def get_group(self, a):
    if a < 0: return -1
    for i in range(len(self.sets)):
      if a in self.sets[i]:
        return i
    return -1
  def add_same_pair(self, a, b):
    ga = self.get_group(a)
    gb = self.get_group(b)
    if ga < 0 and gb < 0:
      self.sets.append(set([a,b]))
    elif ga == gb:
      return
    elif ga >= 0 and gb < 0:
      self.sets[ga].add(b)
    elif ga < 0 and gb >= 0:
      self.sets[gb].add(a)
    else:
      gmin = min(ga,gb)
      gmax = max(ga,gb)
      s = self.sets.pop(gmax)
      self.sets[gmin] = self.sets[gmin].union(s)
  def __str__(self):
    return str(self.sets)

N,K,L = map(int, raw_input().split())
roads = [-1 for i in range(N)]
rails = [-1 for i in range(N)]
road_sets = Sets()
rail_sets = Sets()

for i in range(K):
  p,q = map(int, raw_input().split())
  p -= 1
  q -= 1
  road_sets.add_same_pair(p,q)

for i in range(L):
  r,s = map(int, raw_input().split())
  r -= 1
  s -= 1
  rail_sets.add_same_pair(r,s)

combi_counts = {}
for i in range(N):
  g_road = road_sets.get_group(i)#roads[i])
  g_rail = rail_sets.get_group(i)#rails[i])
  if g_road < 0 or g_rail < 0:
    continue
  if (g_road,g_rail) in combi_counts:
    combi_counts[(g_road,g_rail)] += 1
  else:
    combi_counts[(g_road,g_rail)] = 1

result = []
for i in range(N):
  g_road = road_sets.get_group(i)
  g_rail = rail_sets.get_group(i) 
  if g_road < 0 or g_rail < 0:
    result.append(1)
  else:
    result.append(combi_counts[(g_road,g_rail)])
print ' '.join(map(str, result))