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: Runtime Error

Solution code:
import sys

def dfs(s, t):
    global V, d

    if t in V[s]:
        return True

    d[s] = 1
    for v in V[s]:
        if d[v] == 0:
            if dfs(v, t):
                return True

    return False

lines = sys.stdin.readlines()
if lines[0] == "In preparation.":
    print "In preparation."

n, m = map(int, lines[0].split())
V = [[] for _ in range(n)]
for i in range(1, m + 1):
    c = map(int, lines[i].split())
    V[c[0]].append(c[1])
    V[c[1]].append(c[0])

q = int(lines[m + 1])
for i in range(m + 2, m + q + 2):
    c = map(int, lines[i].split())
    d = [0] * (n)
    if dfs(c[0], c[1]):
        print "yes"
    else:
        print "no"

Submission status: Runtime Error

Solution code:
import sys

def dfs(s, t):
    global V, d

    if t in V[s]:
        return True

    d[s] = 1
    for v in V[s]:
        if d[v] == 0:
            if dfs(v, t):
                return True

    return False

lines = sys.stdin.readlines()
n, m = map(int, lines[0].split())
V = [[] for _ in range(n)]
for i in range(1, m + 1):
    s, t = map(int, lines[i].split())
    V[s].append(t)
    V[t].append(s)

q = int(lines[m + 1])
for i in range(m + 2, m + q + 2):
    s, t = map(int, lines[i].split())
    d = [0] * (n)
    if dfs(s, t):
        print "yes"
    else:
        print "no"

Submission status: Runtime Error

Solution code:
def dfs(s, t):
    global V, d

    if t in V[s]:
        return True

    d[s] = 1
    for v in V[s]:
        if d[v] == 0:
            if dfs(v, t):
                return True

    return False

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

q = int(raw_input())
for _ in range(q):
    s, t = map(int, raw_input().split())
    d = [0] * (n)
    if dfs(s, t):
        print "yes"
    else:
        print "no"

Submission status: Runtime Error

Solution code:
def dfs(i, c):
    global V, C

    if C[i] == -1:
        C[i] = c
    else:
        return

    for v in V[i]:
        dfs(v, c)

n, m = map(int, raw_input().split())
V = [[] for _ in range(n)]
C = [-1] * n
for _ in range(m):
    l, r = map(int, raw_input().split())
    V[l].append(r)
    V[r].append(l)

c = 0
for i in range(n):
    if C[i] == -1:
        dfs(i, c)
        c += 1

q = int(raw_input())
for _ in range(q):
    s, t = map(int, raw_input().split())
    if C[s] == C[t]:
        print "yes"
    else:
        print "no"

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

adj = [[] for i in range(n)]

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

isVisited = [False] * n

CC = [None] * n


def dfs(u, group):
    isVisited[u] = True
    CC[u] = group
    for v in adj[u]:
        if not isVisited[v]:
            dfs(v, group)

def makeCC(group):
    for i in range(n):
        if not isVisited[i]:
            dfs(i, group)
            group += 1

def isConnected(v1, v2):
    if CC[v1] == CC[v2]:
        print('yes')
    else:
        print('no')


makeCC(0)


q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    isConnected(s, t)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

adj = [[] for i in range(n)]

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

isVisited = [False] * n

CC = [None] * n

import sys
sys.setrecursionlimit(10000)

def dfs(u, group):
    isVisited[u] = True
    CC[u] = group
    for v in adj[u]:
        if not isVisited[v]:
            dfs(v, group)

def makeCC(group):
    for i in range(n):
        if not isVisited[i]:
            dfs(i, group)
            group += 1

def isConnected(v1, v2):
    if CC[v1] == CC[v2]:
        print('yes')
    else:
        print('no')


makeCC(0)


q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    isConnected(s, t)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

adj = [[] for i in range(n)]

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

isVisited = [False] * n

CC = [None] * n

import sys
sys.setrecursionlimit(20000)

def dfs(u, group):
    isVisited[u] = True
    CC[u] = group
    for v in adj[u]:
        if not isVisited[v]:
            dfs(v, group)

def makeCC(group):
    for i in range(n):
        if not isVisited[i]:
            dfs(i, group)
            group += 1

def isConnected(v1, v2):
    if CC[v1] == CC[v2]:
        print('yes')
    else:
        print('no')


makeCC(0)


q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    isConnected(s, t)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

adj = [[] for i in range(n)]

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

isVisited = [False] * n

CC = [None] * n

import sys
sys.setrecursionlimit(100000)

def dfs(u, group):
    isVisited[u] = True
    CC[u] = group
    for v in adj[u]:
        if not isVisited[v]:
            dfs(v, group)

def makeCC(group):
    for i in range(n):
        if not isVisited[i]:
            dfs(i, group)
            group += 1

def isConnected(v1, v2):
    if CC[v1] == CC[v2]:
        print('yes')
    else:
        print('no')


makeCC(0)


q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    isConnected(s, t)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

adj = [[] for i in range(n)]

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

isVisited = [False] * n

CC = [None] * n

import sys
sys.setrecursionlimit(1000000)

def dfs(u, group):
    isVisited[u] = True
    CC[u] = group
    for v in adj[u]:
        if not isVisited[v]:
            dfs(v, group)

def makeCC(group):
    for i in range(n):
        if not isVisited[i]:
            dfs(i, group)
            group += 1

def isConnected(v1, v2):
    if CC[v1] == CC[v2]:
        print('yes')
    else:
        print('no')


makeCC(0)


q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    isConnected(s, t)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

adj = [[] for i in range(n)]

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

isVisited = [False] * n

CC = [None] * n

import sys
sys.setrecursionlimit(10000000)

def dfs(u, group):
    isVisited[u] = True
    CC[u] = group
    for v in adj[u]:
        if not isVisited[v]:
            dfs(v, group)

def makeCC(group):
    for i in range(n):
        if not isVisited[i]:
            dfs(i, group)
            group += 1

def isConnected(v1, v2):
    if CC[v1] == CC[v2]:
        print('yes')
    else:
        print('no')


makeCC(0)


q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    isConnected(s, t)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

adj = [[] for i in range(n)]

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

isVisited = [False] * n

CC = [None] * n

import sys
sys.setrecursionlimit(100000000)

def dfs(u, group):
    isVisited[u] = True
    CC[u] = group
    for v in adj[u]:
        if not isVisited[v]:
            dfs(v, group)

def makeCC(group):
    for i in range(n):
        if not isVisited[i]:
            dfs(i, group)
            group += 1

def isConnected(v1, v2):
    if CC[v1] == CC[v2]:
        print('yes')
    else:
        print('no')


makeCC(0)


q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    isConnected(s, t)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

adj = [[] for i in range(n)]

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

isVisited = [False] * n

CC = [None] * n

import sys
sys.setrecursionlimit(10000000000000)

def dfs(u, group):
    isVisited[u] = True
    CC[u] = group
    for v in adj[u]:
        if not isVisited[v]:
            dfs(v, group)

def makeCC(group):
    for i in range(n):
        if not isVisited[i]:
            dfs(i, group)
            group += 1

def isConnected(v1, v2):
    if CC[v1] == CC[v2]:
        print('yes')
    else:
        print('no')


makeCC(0)


q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    isConnected(s, t)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

adj = [[] for i in range(n)]

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

isVisited = [False] * n

CC = [None] * n

import sys
sys.setrecursionlimit(1000000000)

def dfs(u, group):
    isVisited[u] = True
    CC[u] = group
    for v in adj[u]:
        if not isVisited[v]:
            dfs(v, group)

def makeCC(group):
    for i in range(n):
        if not isVisited[i]:
            dfs(i, group)
            group += 1

def isConnected(v1, v2):
    if CC[v1] == CC[v2]:
        print('yes')
    else:
        print('no')


makeCC(0)


q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    isConnected(s, t)

Submission status: Runtime Error

Solution code:
def connected(G,s,t):
    checked = [False]*len(G)
    def main(G,s,t):
        if t in G[s]: return True
        checked[s] = True
        for f in G[s]:
            if checked[f]: continue
            if main(G,f,t): return True
        return False
    return main(G,s,t)


if __name__=='__main__':
    n,m = list(map(int,input().split()))
    G = [[] for _ in range(n)]
    for _ in range(m):
        s,t = list(map(int,input().split()))
        G[s].append(t)
        G[t].append(s)
    q = int(input())
    for _ in range(q):
        s,t = list(map(int,input().split()))
        print('yes' if connected(G,s,t) else 'no')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

def connected(G,s,t):
    checked = [False]*len(G)
    def main(G,s,t):
        if t in G[s]: return True
        checked[s] = True
        for f in G[s]:
            if checked[f]: continue
            if main(G,f,t): return True
        return False
    return main(G,s,t)
        

if __name__=='__main__':
    n,m = list(map(int,input().split()))
    G = [[] for _ in range(n)]
    for _ in range(m):
        s,t = list(map(int,input().split()))
        G[s].append(t)
        G[t].append(s)
    q = int(input())
    for _ in range(q):
        s,t = list(map(int,input().split()))
        print('yes' if connected(G,s,t) else 'no')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

def make_connected_group(G):
    C = [-1]*len(G)
    def main(G,i,grp):
        if C[i] > -1: return
        C[i] = grp
        for j in G[i]: main(G,j,grp)
    group = 0
    for p,cp in enumerate(C): 
        if cp == -1:
            main(G,p,group)
            group += 1
    return C


if __name__=='__main__':
    n,m = list(map(int,input().split()))
    G = [[] for _ in range(n)]
    for i,line in enumerate(sys.stdin):
        if not i < m:
            q = int(line)
            break
        s,t = list(map(int,line.split()))
        G[s].append(t)
        G[t].append(s)
    cn = make_connected_group(G)
    for j,line in enumerate(sys.stdin):
        if not j < q: break
        s,t = list(map(int,line.split()))
        print('yes' if cn[s] == cn[t] else 'no')

Submission status: Runtime Error

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

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

NOT_FOUND = 0
ENQUEUED = 1
FOUND = 2

def dfs(graph, start, end):
    stack = [start]
    status = [NOT_FOUND] * len(graph)

    def loop(stack, status, graph, start, end):
        debug("-------------------")
        debug(stack)
        debug(graph)
        if len(stack) == 0:
            debug(stack)
            return False

        v = stack.pop()
        status[v] = FOUND
        if v == end:
            return True

        edges = graph[v]
        if len(edges) != 0:
            stack.append(v)
            e = edges.pop(0)
            if e == end:
                return True
            if status[e] == NOT_FOUND:
                stack.append(e)
                status[e] = ENQUEUED

        return loop(stack, status, graph, start, end)

    return loop(stack, status, copy.deepcopy(graph), start, end)

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:
        node = queue.pop(0)
        status[node] = FOUND
        edges = graph[node]
        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 dfs(g, s, d):
            print("yes")
        else:
            print("no")

Submission status: Runtime Error

Solution code:
def search(s, t):
    global g
    node = g[s]
    node[1] = 1
    if s == t:
        return True
    else:
        for i in node[0]:
            ch = g[i]
            if ch[1] == 0:
                result = search(i, t)
                if result:
                    return result
        return False

n, m = list(map(int, input().split()))

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

q = int(input())
for i in range(q):
    s, t = list(map(int, input().split()))
    result = search(s, t)
    if result:
        print("yes")
    else:
        print("no")
    for node in g:
        node[1] = 0

Submission status: Runtime Error

Solution code:
def search(s, t, a):
    global g
    a.add(s)
    if s == t:
        return True
    else:
        for ch in g[s]:
            if not (ch in a):
                result = search(ch, t, a)
                if result:
                    return result
        return False

n, m = list(map(int, input().split()))

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

q = int(input())
for i in range(q):
    s, t = list(map(int, input().split()))
    a = set()
    result = search(s, t, a)
    if result:
        print("yes")
    else:
        print("no")
    a.clear()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def assign_color():
    _id = 1
    for m in range(vertices_num):
        if vertices_status_list[m] == -1:
            graph_dfs(m, _id)
            _id += 1
    return None


def graph_dfs(vertex, color):
    vertices_stack = list()
    vertices_stack.append(vertex)
    vertices_status_list[vertex] = color
    while vertices_stack:
        current_vertex = vertices_stack[-1]
        vertices_stack.pop()
        for v in adj_list[current_vertex]:
            if vertices_status_list[v] == -1:
                vertices_status_list[v] = color
                vertices_stack.append(v)
    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num, relation_num = map(int, _input[0].split())

    relation_info = _input[1:relation_num + 1]

    question_num = int(_input[relation_num + 1])
    question_list = _input[relation_num + 2:]

    adj_list = [[] for _ in range(vertices_num)]
    vertices_status_list = [-1] * vertices_num

    for relation in relation_info:
        key, value = int(relation[0]), int(relation[2])
        adj_list[key].append(value)
        adj_list[value].append(key)

    assign_color()

    # print(adj_list)
    for question in question_list:
        start, target = int(question[0]), int(question[2])
        if vertices_status_list[start] == vertices_status_list[target]:
            print("yes")
        else:
            print("no")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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

output:
yes
yes
no

"""

import sys


def assign_color():
    _color = 1
    for v in range(vertices):
        if color[v] == -1:
            graph_dfs(v, _color)
            _color += 1
    return None


def graph_dfs(vertex, _color):
    vertices_stack = list()
    vertices_stack.append(vertex)
    _color[vertex] = _color

    while vertices_stack:
        current_vertex = vertices_stack.pop()
        for v in adj_table[current_vertex]:
            if _color[v] == -1:
                _color[v] = _color
                vertices_stack.append(v)
    return None


def solve():
    for relation in relation_info:
        key, value = map(int, relation)
        adj_table[key].append(value)
        adj_table[value].append(key)

    assign_color()

    # print(adj_list)
    for question in questions:
        start, target = map(int, question)
        if color[start] == color[target]:
            print("yes")
        else:
            print("no")
    return color


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, relations = map(int, _input[0].split())

    relation_info = map(lambda x: x.split(), _input[1:relations + 1])

    q_num = int(_input[relations + 1])
    questions = map(lambda x: x.split(), _input[relations + 2:])

    adj_table = tuple([] for _ in range(vertices))
    color = [-1] * vertices
    ans = solve()

Submission status: Runtime Error

Solution code:
def dfs(G, C, id, color):
    S = []
    S.append(id)
    C[id] = color

    while S:
        u = S[-1]  # ?????¨?¨????????????????????????°??????
        S = S[:-1]  # pop
        for i in range(len(G[u])):
            v = G[u][i]
            if C[v] == -1:
                C[v] = color
                S.append(v)


if __name__ == '__main__':
    # ??????????????\???
    num_of_users, num_of_links = [int(x) for x in input().split(' ')]
    links = []
    for _ in range(num_of_links):
        links.append(list(map(int, input().split(' '))))
    num_of_queries = int(input())
    queries = []
    for _ in range(num_of_queries):
        queries.append(list(map(int, input().split(' '))))

    # ???????????????
    G = [[] for _ in range(11)]
    C = [-1] * 11
    for f, t in links:
        G[f].append(t)
        G[t].append(f)

    color = 1
    for id in range(num_of_users):
        if C[id] == -1:
            dfs(G, C, id, color)
        color += 1

    # ???????????????
    for x, y in queries:
        if C[x] == C[y]:
            print('yes')
        else:
            print('no')

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 * 2)

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def paint_col(adj, cols, i, col):
    cols[i] = col

    for child in adj[i]:
        if cols[child] == 0:
            paint_col(adj, cols, child, col)

def solve():
    n, m = map(int, input().split())
    adj = [[] for i in range(n)]

    for i in range(m):
        s, t = map(int, sys.stdin.readline().split())
        adj[s].append(t)
        adj[t].append(s)

    cols = [0] * n
    col = 1

    for i in range(n):
        if cols[i] == 0:
            paint_col(adj, cols, i, col)
            col += 1

    # debug(cols, locals())

    q = int(input())

    for i in range(q):
        s, t = map(int, sys.stdin.readline().split())

        if cols[s] == cols[t]:
            print('yes')
        else:
            print('no')

    pass

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def paint_col(adj, cols, i, col):
    cols[i] = col

    for child in adj[i]:
        if cols[child] == 0:
            paint_col(adj, cols, child, col)

def solve():
    n, m = map(int, input().split())
    adj = [[] for i in range(n)]

    for i in range(m):
        s, t = map(int, sys.stdin.readline().split())
        adj[s].append(t)
        adj[t].append(s)

    cols = [0] * n
    col = 1

    for i in range(n):
        if cols[i] == 0:
            paint_col(adj, cols, i, col)
            col += 1

    # debug(cols, locals())

    q = int(input())

    for i in range(q):
        s, t = map(int, sys.stdin.readline().split())

        if cols[s] == cols[t]:
            print('yes')
        else:
            print('no')

    pass

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def paint_col(adj, cols, i, col):
    cols[i] = col

    for child in adj[i]:
        if cols[child] == 0:
            paint_col(adj, cols, child, col)

def solve():
    n, m = map(int, input().split())
    adj = [[] for i in range(n)]

    for i in range(m):
        s, t = map(int, sys.stdin.readline().split())
        adj[s].append(t)
        adj[t].append(s)

    cols = [0] * n
    col = 1

    for i in range(n):
        if cols[i] == 0:
            paint_col(adj, cols, i, col)
            col += 1

    # debug(cols, locals())

    q = int(input())

    for i in range(q):
        s, t = map(int, sys.stdin.readline().split())

        if cols[s] == cols[t]:
            print('yes')
        else:
            print('no')

    pass

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def paint_col(adj, cols, i, col):
    nxt = [i]

    while nxt:
        u = nxt[-1]
        try:
            v = next(adj[u])
            if cols[v] == 0:
                cols[v] = col
                nxt.append(v)
        except StopIteration:
            nxt.pop()
            cols[u] = col

def solve():
    n, m = map(int, sys.stdin.readline().split())
    adj = [[] for i in range(n)]

    for i in range(m):
        s, t = map(int, sys.stdin.readline().split())
        adj[s].append(t)
        adj[t].append(s)

    cols = [0] * n
    col = 1
    adj = list(map(iter, adj))

    for i in range(n):
        if cols[i] == 0:
            paint_col(adj, cols, i, col)
            col += 1

    debug(cols, locals())

    q = int(sys.stdin.readline())

    for i in range(q):
        s, t = map(int, sys.stdin.readline().split())

        if cols[s] == cols[t]:
            ans = 'yes'
        else:
            ans = 'no'

        print(ans)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
static const int PLAYERS = 1025;
static const int ROUND = 11;

double ratings[PLAYERS];
double p[PLAYERS][ROUND];
int n;

double win(int p1, int p2) {
	return 1.0 / (1.0 + pow(10, (ratings[p2] - ratings[p1])/400.0));
}

double wp(int i, int k) {
  if (p[i][k] > 0) return p[i][k];
  if (k == 0) return p[i][k] = 1.0;
  /**
   * ?????????????????¢????????°??§????????????????§£?????¨????????????????????????
   */
  int index = i / (int)pow(2.0, k-1);
  int player;
  if (index % 2 == 0) {
    player = (index+1)*pow(2, k-1);
  } else {
    player = (index-1)*pow(2, k-1);
  }

  for (int j = 0; j < pow(2, k-1); j++){
    p[i][k] += wp(i,k-1)*win(i, player + j)*wp(player+j, k-1);
  }
  
  return p[i][k];
}

void solve_by_loop() {
	for (int i = 0; i < (int)pow(2.0, n); i++) {
		p[i][0] = 1.0;
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 0; i < (int)pow(2.0, n); i++) {
			int index = i / (int)pow(2.0, k-1);
			int player;
			if (index % 2 == 0) {
				player = (index+1)*pow(2,k-1);
			} else {
				player = (index-1)*pow(2,k-1);
			}
			for (int j = 0; j < pow(2, k-1); j++) {
				p[i][k] += p[i][k-1]*win(i, player+j)*p[player+j][k-1];
			}
		}
	}
	for (int i = 0; i < pow(2, n); i++) {
		printf("%.10lf\n", p[i][n]);
	}
}
void solve() {
	for (int i = 0; i < (int)pow(2.0, n); i++) {
		printf("%.10lf\n", wp(i, n));
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < (int)pow(2.0, n); i++) {
		cin >> ratings[i];
	}
	solve();
	//solve_by_loop();
	return 0;
}

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())

g = {}
for i in range(m):
    s,t = map(int,input().split())
    val = g.get(s,[])
    val.append(t)
    g[s] = val
    val = g.get(t,[])
    val.append(s)
    g[t] = val

def dfs(g, s, done=[]):
    if s in done:
        return
    done.append(s)
    for c in g[s]:
        dfs(g, c, done)
    return done

q = int(input())

n = set(g.keys())
cc = []
while n != set([]):
    t = n.pop()
    d = dfs(g, t, [])
    cc.append(d)
    n = n - set(d)

for j in range(q):
    s,t = map(int,input().split())
    k = True
    for c in cc:
        if s in c and t in c:
            print('yes')
            k = False
            break
    if k: print('no')

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())

g = {}
for i in range(m):
    s,t = map(int,input().split())
    val = g.get(s,[])
    val.append(t)
    g[s] = val
    val = g.get(t,[])
    val.append(s)
    g[t] = val

count = 0
def dfs(g, s, done=[]):
    global count
    count += 1
    if s in done:
        return
    done.append(s)
    for c in g[s]:
        dfs(g, c, done)
    return done

q = int(input())

n = set(g.keys())
cc = []
from sys import setrecursionlimit
setrecursionlimit(1500)
while n != set([]):
    t = n.pop()
    d = dfs(g, t, [])
    cc.append(d)
    n = n - set(d)

for j in range(q):
    s,t = map(int,input().split())
    k = True
    for c in cc:
        if s in c and t in c:
            print('yes')
            k = False
            break
    if k: print('no')

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())

g = {}
for i in range(m):
    s,t = map(int,input().split())
    val = g.get(s,[])
    val.append(t)
    g[s] = val
    val = g.get(t,[])
    val.append(s)
    g[t] = val

color = 1
done = [-1] + [-1] * m

def dfs(g, s):
    done[s] = color
    stack = [s]
    while stack != []:
        t = stack.pop()
        for c in g[t]:
            if done[c] == -1:
                done[c] = color
                stack.append(c)
    return

q = int(input())

n = set(g.keys())

for v in range(m):
    if done[v] == -1:
        dfs(g,v)
        color += 1

for j in range(q):
    s,t = map(int,input().split())
    if done[s] == done[t]:
        print('yes')
    else: print('no')

Submission status: Runtime Error

Solution code:
import sys

def srch(i, end, l, Dst, Lng):
    if Lng[i] != -1 and Lng[i] < l:
        return
    Lng[i] = l
    if i == end:
        return
    if Dst[i] is not None and len(Dst[i]) > 0:
        for c in Dst[i]:
            srch(c, end, l+1, Dst, Lng)

def main():
    istr = sys.stdin.read()
    ilist = []
    for i in istr.splitlines():
        ilist.append(list(map(int,i.split())))
    #print(ilist)
    unum, fnum = ilist[0]

    Dst = [[] for i in range(unum)]
    fnum += 1
    for n in range(1, fnum):
        uid, fid = ilist[n]
        Dst[uid].append(fid)
        Dst[fid].append(uid)
    
    qnum = ilist[fnum][0]
    fnum += 1
    #print("fnum={} qnum={}".format(fnum,qnum))
    for q in range(fnum, (fnum + qnum)):
        id1, id2 = ilist[q]
        Lng = [-1] * (fnum)
        #print("[{}] id1={:2} id2={:2} Dst:{} Lng:{}".format(q,id1, id2, Dst, Lng))
        srch(id1, id2, 0, Dst, Lng)
        if Lng[id2] != -1:
            print("yes")
        else:
            print("no")

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m = map(int,raw_input().split())
    A = [[] for i in xrange(n)]
    for i in xrange(m):
        s, t = map(int,raw_input().split())
        A[s].append(t)
        A[t].append(s)

    q = input()
    a =[0]*q
    for i in xrange(q):
        s, t = map(int,raw_input().split())
        c = [-1]*n
        dfs(s,t,c,A)
        if c[t] == -1:
            a[i] = 'no'
        else:
            a[i] = 'yes'

    for i in a:
        print i
        
def dfs(u,t,color,A):
    color[u] = 0
    for i in A[u]:
        if i == t:
            color[t] = 1
            break
        elif (color[i] == -1):
            dfs(i,t,color,A)
    color[u] = 1

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def bfs(graph, start, goal, connection):
    visited = {start: None}
    unvisited = [start]
    while unvisited:
        now = unvisited[0]
        if now == goal or connection[1000000*now + goal] == 1:
            connection[1000000*start + goal] = 1
            return "yes"
        unvisited = unvisited[1:]
        for next in graph[now][1:]:
            if not (next in visited):
                unvisited.append(next)
                visited[next] = now
    return "no"

n, m = map(int, input().split())
g = [[i] for i in range(n)]
c = {}

for i in range(m):
    inp = list(map(int, input().split()))
    g[inp[0]].append(inp[1])
    g[inp[1]].append(inp[0])

q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    print(bfs(g, s, t, c))