Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Connected Components

  Write a program which reads relations in a SNS (Social Network Service), and judges that given pairs of users are reachable each other through the network.

Input

  In the first line, two integer $n$ and $m$ are given. $n$ is the number of users in the SNS and $m$ is the number of relations in the SNS. The users in the SNS are identified by IDs $0, 1, ..., n-1$.

  In the following $m$ lines, the relations are given. Each relation is given by two integers $s$ and $t$ that represents $s$ and $t$ are friends (and reachable each other).

  In the next line, the number of queries $q$ is given. In the following $q$ lines, $q$ queries are given respectively. Each query consists of two integers $s$ and $t$ separated by a space character.

Output

  For each query, print "yes" if $t$ is reachable from $s$ through the social network, "no" otherwise.

Constraints

$2 \leq n \leq 100,000$

$0 \leq m \leq 100,000$

$1 \leq q \leq 10,000$

Sample Input

10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3

Sample Output

yes
yes
no



Sample input:
10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3


Sample output:
yes
yes
no

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque


class LinkedList:
    def __init__(self, n):
        self.n = n
        self.ll = [[] for _ in range(self.n)]

    def link(self, u, v, direction=False):
        self.ll[u].append(v)
        if not direction:
            self.ll[v].append(u)

    def check(self, start, goal):
        states = [0] * self.n
        queue = deque([start])

        while queue:
            u = queue.popleft()
            # if states[u]:
            #     continue
            # else:
            states[u] = 1

            for v in self.ll[u]:
                if v == goal:
                    print('yes')
                    return

                if states[v]:
                    continue
                else:
                    queue.append(v)

        else:
            print('no')
            return


if __name__ == '__main__':
    n, m = map(int, input().split())
    ll = LinkedList(n)

    for _ in range(m):
        u, v = map(int, input().split())
        ll.link(u, v)

    q = int(input())
    for _ in range(q):
        u, v = map(int, input().split())
        ll.check(u, v)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(50000)
def dfs(s):
    global t
    if s == t:
        return True
    DP[s]=1
    for i in F[s]:
        if not DP[i]:
            if dfs(i):
                return True
    return False
    
n,m = [int(i) for i in input().split()]
F = [{} for i in range(n)]
for _ in range(m):
    i,j = [int(i) for i in input().split()]
    F[i][j] = 1
    F[j][i] = 1
q = int(input())
for i in range(q):
    DP = [0]*n
    s,t = [int(i) for i in input().split()]
    if dfs(s):
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = [int(i) for i in input().split()]
F = [{} for i in range(n)]
for _ in range(m):
    i,j = [int(i) for i in input().split()]
    F[i][j] = 1
    F[j][i] = 1
q = int(input())
for i in range(q):
    DP = [0]*n
    d = deque()
    s,t = [int(i) for i in input().split()]
    d.append(s)
    flag = False
    while(len(d)>0):
        tmp = d.pop()
        DP[tmp] = 1
        if tmp == t:
            flag = True
            break
        else:
            for i in F[tmp]:
                if not DP[i]:
                    d.append(i)
    if flag:
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8

n, m = map(int,input().split())
List = [[] for i in range(n)]
colorOriginal = ["white" for i in range(n)]

for i in range(m):
    s,t = map(int,input().split())
    List[s].append(t)
    List[t].append(s)


def search(a, target):
    color = colorOriginal[:]
    Q = [a]
    color[a] = "black"
    while Q != []:
        top = Q[0]
        if top == target:
            print("yes")
            break
        for i in List[top]:
            if color[i] == "white":
                Q.append(i)
                color[i] = "gray"
        color[top] = "black"
        Q.pop(0)
    else:
        print("no")

ques = int(input())
for i in range(ques):
    a, target = map(int,input().split())
    search(a, target)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8

n, m = map(int,input().split())
List = [[] for i in range(n)]
colorOriginal = ["white" for i in range(n)]

for i in range(m):
    s,t = map(int,input().split())
    List[s].append(t)
    List[t].append(s)



class DoublyLinkedList():
    def __init__(self, key, l=None, r=None):
        self.l = l
        self.r = r
        self.key = key

def Insert(key,sentinel):
    obj = DoublyLinkedList(key)
    left = sentinel.l
    left.r = obj
    obj.l = left
    obj.r = sentinel
    sentinel.l = obj

def deleteFirst(sentinel):
    right = sentinel.r
    sentinel.r = right.r
    right.r.l = sentinel


def search(a, target):
    sentinel = DoublyLinkedList(None)
    sentinel.l = sentinel
    sentinel.r = sentinel
    
    color = colorOriginal[:]
    Insert(a, sentinel)
    color[a] = "black"
    while sentinel.r.key != None:
        top = sentinel.r.key
        if top == target:
            print("yes")
            break
        for i in List[top]:
            if color[i] == "white":
                Insert(i, sentinel)
                color[i] = "gray"
        color[top] = "black"
        deleteFirst(sentinel)
    else:
        print("no")

ques = int(input())
for i in range(ques):
    a, target = map(int,input().split())
    search(a, target)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


user_num,rer_num=map(int,input().split())
graph=[[] for loop in range(user_num)]

for loop in range(rer_num):
    user1,user2=map(int,input().split())
    graph[user1].append(user2)
    graph[user2].append(user1)

#group[user1]はuser1が属するグループ.同じグループに属するuser同士は互いに到達可能
group=[-1]*user_num

que=deque([])
que.append(0)
tmp_group=0
for user in range(user_num):
    if(group[user]==-1):
        que.append(user)
        group[user]=tmp_group
        while(1):
            user1=que.popleft()
            for user2 in graph[user1]:
                if(group[user2]!=-1):
                    que.append(user2)
                    group[user2]=tmp_group
            if(len(que)==0):
                tmp_group+=1
                break


for loop in range(int(input())):
    user1,user2=map(int(input()))
    if(group[user1]==group[user2]):
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque

def read_graph(n, k):
    A = [ [] for _ in range(n) ]
    for _ in range(k):
        line = stdin.readline().strip().split()
        A[int(line[0])].append(int(line[1]))
        A[int(line[1])].append(int(line[0]))
    return A

def bfs_ctrl(n, A, s, t):
    color = ["WHITE"] * n
    d = [-1] * n
    Q = deque([])

    def bfs(s):
        nonlocal color
        nonlocal d
        nonlocal Q
        color[s] = "GRAY"
        d[s] = 0
        Q.append(s)

        while Q:
            u = Q.popleft()
            for v in A[u]:
                if color[v] == "WHITE":
                    color[v] = "GRAY"
                    d[v] = d[u] + 1
                    Q.append(v)

            color[u] = "BLACK"

    bfs(s)
    if d[t] != -1:
        print("yes")
    else:
        print("no")

def read_and_print_connection(m):
    for _ in range(m):
        line = stdin.readline().strip().split()
        s = int(line[0])
        t = int(line[1])
        bfs_ctrl(n, A, s, t)

n, k = [int(i) for i in input().split()]
A = read_graph(n, k)
m = int(input())
read_and_print_connection(m)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
# print('n:', n, 'm:', m)
A = [[0 for i in range(n)] for j in range(n)]
visited = [0 for i in range(n)]

for i in range(m):
    u, v = list(map(int, input().split()))
    # print(u, v)
    A[u][v] = 1
    A[v][u] = 1
# print(A)

q = int(input())
# print('q:', q)


def dfs(s):
    # print('visit', s)
    if s is None:
        return
    visited[s] = 1
    for v in range(n):
        # print('candidate:', v)
        if A[s][v] == 1 and visited[v] == 0:
            dfs(v)

def can_go(s, t):
    # print(s, '->', t, '----------')
    global visited
    visited = [0 for i in range(n)]
    dfs(s)
    # print(visited)
    if visited[t] == 1:
        return True
    else:
        return False

for i in range(q):
    s, t = map(int, input().split())
    if can_go(s, t):
        print('yes')
    else:
        print('no')

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
sys.setrecursionlimit(100000)

n, m = [int(ele) for ele in input().split()]
graph = [[i] for i in range(n)]
grps = [-1] * n
s = [-1] * (m+1)
t = [-1] * (m+1)

for _ in range(m):
    k, l = [int(ele) for ele in input().split()]
    graph[k].append(l)
    graph[l].append(k)

q = int(input())

s_q = [-1] * (q)
s_t = [-1] * (q)

for i in range(q):
    s_q[i], s_t[i] = [int(ele) for ele in input().split()]


yet = [ele for ele in range(n)]
stack = collections.deque()


def main():
    global graph, grps
    grouping()

    for src, dst in zip(s_q, s_t):
        if grps[src] == grps[dst]:
            print("yes")
        else:
            print("no")


def grouping():
    global yet, stack, grps, tmp
    tmp = 97
    while yet:
        stack.clear()
        stack.appendleft(yet[0])  # 常にmin(yet) = yet[0]
        dfs(stack)
        tmp += 1


def dfs(stack):
    global yet, graph, grps, tmp
    if not stack:
        return

    n = stack[0]
    grps[n] = chr(tmp)
    yet.remove(n)

    for ele in graph[n][1:]:
        if ele in yet:  # 未訪問なら
            stack.appendleft(ele)
            dfs(stack)
    else:
        stack.popleft()


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, m = map(int, input().split())
graph = [[] for _ in range(n)]

global visited 
visited = [0 for _ in range(n)]

def input_graph(m):
  for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

def dfs(node_id):
  
  for ad_node in graph[node_id]:
    if visited[ad_node] == 1:
      continue
    visited[ad_node] = 1
    dfs(ad_node)

if __name__ == "__main__":
  input_graph(m)
  q_num = int(input())
  for _ in range(q_num):
    visited = [0 for _ in range(n)]
    s, t = map(int, input().split())
    dfs(s)
    if visited[t]:
      print("yes")
    else:
      print("no")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(1000000)
n, m = map(int, input().split())
graph = [[] for _ in range(n)]

global visited 
visited = [0 for _ in range(n)]
global Q, S, T

S = [0] #訪れた順
T = []
visited[0] = 1 #開始位置はすでに訪れたことにする

def input_graph(m):
  for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

def dfs():
  global Q, S
  while Q:
    node_id = Q.pop()

    for ad_node in graph[node_id]:
      if visited[ad_node] == 1:
        continue
      visited[ad_node] = 1
      S.append(ad_node)
      Q.append(ad_node)


"""
def dfs(node_id):
  
  for ad_node in graph[node_id]:
    if visited[ad_node] == 1:
      continue
    visited[ad_node] = 1
    dfs(ad_node)
"""
if __name__ == "__main__":
  input_graph(m)
  q_num = int(input())
  for _ in range(q_num):
    visited = [0 for _ in range(n)]
    s, t = map(int, input().split())
    Q = deque([s])
    dfs()
    if visited[t]:
      print("yes")
    else:
      print("no")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
n, m = map(int, input().split())
ALL = [0] * n
Graph = []
for i in range(m):
    s, t = map(int, input().split())
    if ALL[s] == 0 and ALL[t] == 0:
        Graph.append(set([s, t]))
    elif ALL[s] == 0:
        for g in Graph:
            if t in g:
                g.add(s)
                break
    elif ALL[t] == 0:
        for g in Graph:
            if s in g:
                g.add(t)
                break
    else:
        sg = None
        tg = None
        for g in Graph:
            if s in g:
                sg = g
            if t in g:
                tg = g

        if sg is not tg:
            sg.update(tg)
            Graph.remove(tg)

    ALL[s] = 1
    ALL[t] = 1
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    for g in Graph:
        if s in g and t in g:
            print('yes')
            break
    else:
        print('no')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
n, m = map(int, input().split())

e = [None] * n

for i in range(m):
    s, t = map(int, input().split())
    if e[s] == None and e[t] == None:
        a = {s, t}
        e[s] = e[t] = a
    elif e[s] == None:
        e[t].add(s)
        e[s] = e[t]
    elif e[t] == None:
        e[s].add(t)
        e[t] = e[s]
    else:
        a = e[s] | e[t]
        for j in a:
            e[j] = a

q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    if e[s] != None and t in e[s]:
        print('yes')
    else:
        print('no')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, raw_input().split())
G = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    s, t = map(int, raw_input().split())
    G[s][t] = 1
    G[t][s] = 1

for i in range(n):
    for j in range(n):
        for k in range(n):
            if G[j][k] == 1:
                for l in range(n):
                    if G[k][l] == 1:
                        G[j][l] = 1
                        G[l][j] = 1

q = int(raw_input())
ans = ["no" for i in range(q)]
for i in range(q):
    s, t = map(int, raw_input().split())
    if G[s][t] == 1:
        ans[i] = "yes"
for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, raw_input().split())
G = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    s, t = map(int, raw_input().split())
    G[s][t] = 1
    G[t][s] = 1

for i in range(n):
    for j in range(n):
        for k in range(n):
            if G[j][k] == 1:
                for l in range( n):
                    if G[k][l] == 1:
                        G[j][l] = 1
                        G[l][j] = 1

q = int(raw_input())
ans = ["no" for i in range(q)]
for i in range(q):
    s, t = map(int, raw_input().split())
    if G[s][t] == 1:
        ans[i] = "yes"
for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)

n, m = map(int, input().split())
g = [set() for _ in range(n)]

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def find(s, t):
    global g
    visited = [0] * n

    def dfs(i):
        visited[i] = 1
        if i == t:
            return True
        for f in g[i]:
            if not visited[f]:
                if dfs(f):
                    return True
        return False

    return dfs(s)


q = int(input())
while q:
    s, t = map(int, input().split())
    print('yes' if find(s, t) else 'no')
    q -= 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
g = [set() for _ in range(n)]

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def find(s, t):
    global g
    visited = [0] * n
    queue = deque()
    queue.append(s)

    while queue:
        i = queue.popleft()
        if i == t:
            return True
        for f in g[i]:
            if not visited[f]:
                visited[f] = 1
                queue.append(f)
    return False


q = int(input())
while q:
    s, t = map(int, input().split())
    print('yes' if find(s, t) else 'no')
    q -= 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
g = [set() for _ in range(n)]

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def find(s, t):
    global g
    queue = deque()
    queue.append((0, s))
    queue.append((1, t))
    visited = ([0] * n, [0] * n)
    visited[0][s] = 1
    visited[1][t] = 1

    while queue:
        st, i = queue.popleft()
        if visited[not st][i]:
            return True
        for f in g[i]:
            if not visited[st][f]:
                visited[st][f] = 1
                queue.append((st, f))
    return False


q = int(input())
while q:
    s, t = map(int, input().split())
    print('yes' if find(s, t) else 'no')
    q -= 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
g = [set() for _ in range(n)]

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def find(s, t):
    global g
    queue = deque()
    queue.append((0, s))
    queue.append((1, t))
    visited = ([0] * n, [0] * n)
    visited[0][s] = 1
    visited[1][t] = 1

    def remember(visited, new):
        for i, v in enumerate(visited):
            if v:
                g[new].add(i)
                g[i].add(new)
        visited[new] = 1

    while queue:
        st, i = queue.popleft()
        for f in g[i]:
            if visited[not st][f]:
                return True
            if not visited[st][f]:
                remember(visited[st], f)
                queue.append((st, f))
    return False


q = int(input())
while q:
    s, t = map(int, input().split())
    print('yes' if find(s, t) else 'no')
    q -= 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
g = [set() for _ in range(n)]

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def find(s, t):
    global g
    queue = deque()
    queue.append((0, s))
    queue.append((1, t))
    visited = (set(), set())
    visited[0].add(s)
    visited[1].add(t)

    def remember(visited, new):
        g[new] |= visited
        for v in visited:
            g[v].add(new)
        visited.add(new)

    while queue:
        st, i = queue.popleft()
        for f in g[i]:
            if f in visited[not st]:
                return True
            if f not in visited[st]:
                remember(visited[st], f)
                queue.append((st, f))
    return False


q = int(input())
while q:
    s, t = map(int, input().split())
    print('yes' if find(s, t) else 'no')
    q -= 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
g = [set() for _ in range(n)]

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def find(s, t):
    global g
    queue = deque()
    queue.append((0, s))
    queue.append((1, t))
    visited = ([0] * n, [0] * n)
    visited[0][s] = 1
    visited[1][t] = 1

    while queue:
        st, i = queue.popleft()
        for f in g[i]:
            if visited[not st][f]:
                g[s].add(t)
                g[t].add(s)
                return True
            if not visited[st][f]:
                visited[st][f] = 1
                queue.append((st, f))
    return False


q = int(input())
while q:
    s, t = map(int, input().split())
    print('yes' if find(s, t) else 'no')
    q -= 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
g = [set() for _ in range(n)]
gids = [0] * n

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def search(s, gid):
    global g, gids
    queue = deque()
    queue.append(s)
    visited = [0] * n
    visited[s] = 1
    gids[s] = gid

    while queue:
        i = queue.popleft()
        for f in g[i]:
            if not visited[f]:
                visited[f] = 1
                gids[f] = gid
                queue.append(f)


gid = 1
for i in range(n):
    if gids[i]:
        continue
    search(i, gid)
    gid += 1

q = int(input())
while q:
    s, t = map(int, input().split())
    gs, gt = gids[s], gids[t]
    print('yes' if gs and gt and gs == gt else 'no')
    q -= 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
g = [set() for _ in range(n)]
group_ids = [0] * n

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def search(s, gid):
    global g, group_ids
    queue = set()
    queue.add(s)
    visited = [0] * n
    visited[s] = 1
    group_ids[s] = gid

    while queue:
        i = queue.pop()
        for f in g[i]:
            if not visited[f]:
                visited[f] = 1
                group_ids[f] = gid
                queue.add(f)


gid = 1
for i in range(n):
    if group_ids[i]:
        continue
    search(i, gid)
    gid += 1

q = int(input())
while q:
    s, t = map(int, input().split())
    gs, gt = group_ids[s], group_ids[t]
    print('yes' if gs and gt and gs == gt else 'no')
    q -= 1

Submission status: Time Limit Exceeded

Solution code:
def DFS(s):
    flag[s] = 1
    group[s] = j
    for i in range(n):
        if i in G[s] and flag[i] == 0:
            DFS(i)

n, m = map(int, input().split())
G = [[] for j in range(n)]

for i in range(m):
    s, t = map(int, input().split())
    G[s].append(t)
    G[t].append(s)

group = [[] for i in range(n)]
flag = [0 for i in range(n)]
j = 0
for i in range(n):
    if flag[i] == 0:
        DFS(i)
        j += 1

q = int(input())
for i in range(q):
    s, t = input().split()
    if group[int(s)] == group[int(t)]:
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
def DFS(s):
    flag[s] = 1
    group[s] = j
    for i in range(n):
        if i in G[s] and flag[i] == 0:
            DFS(i)

n, m = map(int, input().split())
G = [[] for j in range(n)]

for i in range(m):
    s, t = map(int, input().split())
    G[s].append(t)
    G[t].append(s)

group = [[] for i in range(n)]
flag = [0 for i in range(n)]
j = 0
for i in range(n):
    if flag[i] == 0:
        DFS(i)
        j += 1

q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    if group[s] == group[t]:
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
def DFS(s):
    group[s] = j
    for i in range(n):
        if i in G[s] and group[i] == 0:
            DFS(i)

n, m = map(int, input().split())
G = [[] for j in range(n)]

for i in range(m):
    s, t = map(int, input().split())
    G[s].append(t)
    G[t].append(s)

group = [0 for i in range(n)]
j = 1
for i in range(n):
    if group[i] == 0:
        DFS(i)
        j += 1

q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    if group[s] == group[t]:
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
def DFS(s, j):
    group[s] = j
    for i in range(n):
        if i in G[s] and group[i] == 0:
            DFS(i, j)

n, m = map(int, input().split())
G = [[] for j in range(n)]

for i in range(m):
    s, t = map(int, input().split())
    G[s].append(t)
    G[t].append(s)

group = [0 for i in range(n)]
j = 1
for i in range(n):
    if group[i] == 0:
        DFS(i, j)
        j += 1

q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    if group[s] == group[t]:
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
def DFS(s):
    flag[s] = 1
    group[j].append(s)
    for i in range(n):
        if i in G[s] and flag[i] == 0:
                DFS(i)
 

n, m = map(int, input().split())
G = [[] for j in range(n)]
for i in range(m):
    s, t = map(int, input().split())
    G[s].append(t)
    G[t].append(s)

flag = [0 for i in range(n)]
group = []
j = 0
for i in range(n):
    if flag[i] == 0:
        group.append([])
        DFS(i)
        j += 1

q = int(input())
ans = ["no" for i in range(q)]
for i in range(q):
    s, t = map(int, input().split())
    for j in range(len(group)):
        if s in group[j] and t in group[j]:
            ans[i] = "yes"
for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
G = [[] for j in range(n)]
for i in range(m):
    s, t = map(int, input().split())
    G[s].append(t)
    G[t].append(s)

group = [[] for i in range(n)]
c = 0
for i in range(n):
    if not i in group:
        que = [i]
        group[i] = c
        while len(que) > 0:
            u = que[0]
            for j in G[u]:
                if not j in group:
                    group[j] = que.append(j)
            del que[0]
        c += 1

q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    if group[s] == group[t]:
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
def scanu(t):
    a = list(map(t,input().split()))
    return a

def breathSerch(P,N,start):
    n=len(P)-1
    m=1
    QQ=[N[start]]
    while(QQ != []):
        R=[]
        for Q in QQ:
            for i in range(1,n+1):
                if Q[i]==1 and P[i]==-1:
                    P[i]=m
                    R.append(N[i])
        QQ = R
        m=m+1

(n,m) = scanu(int)
A = [[0 for j in range(n+1)] for i in range(n+1)]
for i in range(m):
    (s,t)= scanu(int)
    A[s+1][t+1]=1
    A[t+1][s+1]=1

q = int(input())

for i in range(q):
    (s,t) = scanu(int)
    P=[-1 for i in range(n+1)]
    P[s+1]=0
    breathSerch(P,A,s+1)
    if P[t+1]!=-1:
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
def scanu(t):
    a = list(map(t,input().split()))
    return a

def breathSerch(P,N,start,end):
    n=len(P)-1
    m=1
    QQ=[N[start]]
    while(QQ != []):
        R=[]
        for Q in QQ:
            for i in range(1,n+1):
                if Q[i]==1 and P[i]==-1:
                    if i == end:
                        return True
                    P[i]=m
                    R.append(N[i])

        QQ = R
        m=m+1
    return False

(n,m) = scanu(int)
A = [[0 for j in range(n+1)] for i in range(n+1)]
for i in range(m):
    (s,t)= scanu(int)
    A[s+1][t+1]=1
    A[t+1][s+1]=1

q = int(input())

for i in range(q):
    (s,t) = scanu(int)
    P=[-1 for i in range(n+1)]
    P[s+1]=0
    res = breathSerch(P,A,s+1,t+1)
    if res or P[t+1]!=-1:
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
def connect(s,t):
    global ct
    if color[s]!="white" or ct==1:
        return
    color[s]="grey"
    for i in fr[s]:
        if i==-1:
            continue
        elif i==t:
             ct+=1
        else:
            connect(i,t)

n,m=map(int,raw_input().split())
fr=[[-1]*n for i in xrange(n)]
for i in xrange(m):
    s,t=map(int,raw_input().split())
    fr[s][t]=t
    fr[t][s]=s
q=input()
for i in xrange(q):
    ct=0
    color=["white"]*n
    s,t=map(int,raw_input().split())
    connect(s,t)
    if ct==0:
        print('no')
    else:
        print('yes')

Submission status: Time Limit Exceeded

Solution code:
def connect(o,s,t):
    global ct
    if color[s]!="white" or ct==1:
        return
    if fr[o][t]==t:
        ct+=1
    color[s]="grey"
    for i in fr[s]:
        if i==-1:
            continue
        elif i==t:
             ct+=1
             break
        else:
            fr[o][i]=i
            fr[i][o]=s
            connect(o,i,t)
            
n,m=map(int,raw_input().split())
fr=[[-1]*n for i in xrange(n)]
for i in xrange(m):
    s,t=map(int,raw_input().split())
    fr[s][t]=t
    fr[t][s]=s
q=input()
for i in xrange(q):
    ct=0
    color=["white"]*n
    s,t=map(int,raw_input().split())
    connect(s,s,t)
    if ct==0:
        print('no')
    else:
        print('yes')
        fr[s][t]=t
        fr[t][s]=s

Submission status: Time Limit Exceeded

Solution code:
def connect(o,s,t):
    global ct
    if color[s]!="white" or ct!=0:
        return
    if fr[o][t]==t:
        ct+=1
    color[s]="grey"
    for i in fr[s]:
        if i==-1:
            continue
        elif i==t or ct!=0:
             ct+=1
             break
        else:
            fr[o][i]=i
            fr[i][o]=o
            connect(o,i,t)
            
n,m=map(int,raw_input().split())
fr=[[-1]*n for i in xrange(n)]
for i in xrange(m):
    s,t=map(int,raw_input().split())
    fr[s][t]=t
    fr[t][s]=s
q=input()
for i in xrange(q):
    ct=0
    color=["white"]*n
    s,t=map(int,raw_input().split())
    connect(s,s,t)
    if ct==0:
        print('no')
    else:
        print('yes')
        fr[s][t]=t
        fr[t][s]=s

Submission status: Time Limit Exceeded

Solution code:
def cover(V, i):
    for j in range(i + 1, len(V)):
        if V[i] & V[j]:
            V.append(V[i] | V[j])
            del V[j], V[i]
            return True

n, m = map(int, raw_input().split())
V = []
for _ in range(m):
    v = set(map(int, raw_input().split()))
    V.append(v)

flag = True
while flag:
    flag = False
    for i in range(len(V)):
        if cover(V, i):
            flag = True
            break

q = int(raw_input())
for _ in range(q):
    s, t = map(int, raw_input().split())
    flag = True
    for v in V:
        if s in v:
            if t in v:
                print "yes"
            else:
                print "no"
            flag = False
            break
    if flag:
        print "no"

Submission status: Time Limit Exceeded

Solution code:
def cover(V, i):
    for j in range(i + 1, len(V)):
        if V[i] & V[j]:
            V[i] |=  V[j]
            del V[j]
            return True

n, m = map(int, raw_input().split())
V = []
for _ in range(m):
    v = set(map(int, raw_input().split()))
    V.append(v)

flag = True
while flag:
    flag = False
    for i in range(len(V)):
        if cover(V, i):
            flag = True
            break

q = int(raw_input())
for _ in range(q):
    s, t = map(int, raw_input().split())
    flag = True
    for v in V:
        if s in v:
            if t in v:
                print "yes"
            else:
                print "no"
            flag = False
            break
    if flag:
        print "no"

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf_8 -*-

level = False
def debug(v):
    if level:
        print(v)

NOT_FOUND = 0
ENQUEUED = 1
FOUND = 2

def bfs(graph, start, target):
    debug(graph)
    if start == target:
        return True
    
    queue = []
    status = [NOT_FOUND] * len(graph)
    queue.append(start)

    while len(queue) != 0:
        debug("----------------------------")
        node = queue.pop(0)
        status[node] = FOUND
        edges = graph[node]
        debug(queue)
        debug(status)
        debug(edges)
        for e in edges:
            if e == target:
                return True
            if status[e] == NOT_FOUND:
                status[e] = ENQUEUED
                queue.append(e)

    return False

if __name__ == "__main__":
    n, m = [int(x) for x in input().split()]

    g = [[] for i in range(n)]
    for i in range(m):
        u, e = [int(x) for x in input().split()]
        g[u].append(e)
        g[e].append(u)

    n = int(input())
    for i in range(n):
        s, d = [int(x) for x in input().split()]
        if bfs(g, s, d):
            print("yes")
        else:
            print("no")