Problem:


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

Breadth First Search

  Write a program which reads an directed graph $G = (V, E)$, and finds the shortest distance from vertex $1$ to each vertex (the number of edges in the shortest path). Vertices are identified by IDs $1, 2, ... n$. 

Input

  In the first line, an integer $n$ denoting the number of vertices, is given. In the next $n$ lines, adjacent lists of vertex $u$ are given in the following format:

$u$ $k$ $v_1$ $v_2$ ... $v_k$

$u$ is ID of the vertex and $k$ denotes its degree.$v_i$ are IDs of vertices adjacent to $u$.

Constraints

$1 \leq n \leq 100$

Output

  For each vertex $u$, print $id$ and $d$ in a line. $id$ is ID of vertex $u$ and $d$ is the distance from vertex $1$ to vertex $u$. If there are no path from vertex $1$ to vertex $u$, print -1 as the shortest distance. Print in order of IDs.

Sample Input 1

4
1 2 2 4
2 1 4
3 0
4 1 3

Sample Output 1

1 0
2 1
3 2
4 1

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.



Sample input:
4
1 2 2 4
2 1 4
3 0
4 1 3


Sample output:
1 0
2 1
3 2
4 1

Submission status: Runtime Error

Solution code:


n = int(raw_input())
d = [100 for i in range(n)]
G = [0 for i in range(n)]
v = [[0 for i in range(n)] for j in range(n)]
  
def Bread(s):
    for e in range(n):
        if v[s][e] == 1:
            if d[e] > d[s] + 1:
                d[e] = d[s]+1
                Bread(e)
  
for i in range(n):
    G = map(int, raw_input().split())
 
    for j in range(G[1]):
        v[G[0]-1][G[j+2]-1] = 1
 
d[0] = 0
  
for i in range(n):
    Bread(i)
 
for i in range(n):
    if d[i] == 100:
        d[i] = -1
 
for i in range(n):
    print i+1, d[i]
 

 
Compile Error Logs: 

You are not authorized to see the message. 
 
 
Status 
Judge: 8/8  Python  CPU: 00.04 sec  Memory: 6492 KB  Length: 531 B  2016-02-02 22:02  2016-02-02 22:02  
Results for testcases 
Case # Verdict CPU Time Memory In Out Case Name 
 Case #1: : Accepted  00.01 sec 6476 KB 40 B 26 B 1.in 
 Case #2: : Accepted  00.00 sec 6280 KB 20 B 12 B 2.in 
 Case #3: : Accepted  00.00 sec 6472 KB 75 B 41 B 3.in 
 Case #4: : Accepted  00.00 sec 6304 KB 62 B 20 B 4.in 
 Case #5: : Accepted  00.00 sec 6320 KB 158 B 96 B 5.in 
 Case #6: : Accepted  00.00 sec 6364 KB 355 B 152 B 6.in 
 Case #7:

Submission status: Runtime Error

Solution code:
n = int(input())

adj = [None]
for i in range(n):
    adj_i = list(map(int, input().split()[2:]))
    adj.append(adj_i)

distance = [None] + [-1] * n

def bfs(u, d):
    pd = distance[u]
    if pd == -1 or d < pd:
        distance[u] = d
    for v in adj[u]:
        bfs(v, d + 1)


bfs(1, 0)

for i, d in enumerate(distance[1:], start=1):
    print(i, d)

Submission status: Runtime Error

Solution code:
def BFS(G):
    ans = [0] + [[i+1,-1] for i in range(len(G))]
    def main(G,i,d):
        ans[i] = [i, d]
        for j in G[i-1][2:]: main(G,j,d+1)
    main(G,1,0)
    return ans[1:]


if __name__=='__main__':
    n = int(input())
    G = [list(map(int,input().split())) for _ in range(n)]
    for out in BFS(G): print(*out)

Submission status: Runtime Error

Solution code:
from collections import deque


def bfs(root):
    Q = deque()
    distance[root] = 0
    Q.append(root)
    i = root
    while len(Q) > 0:
        for v in n:
            if adjMat[i][v] == 1 and color[v] == 'white':
                Q.append(v)
                color[v] = 'gray'
                distance[v] = distance[i] + 1
        color[i] = 'black'
        i = Q.popleft()


n = int(input())
adjMat = [[0] * n for _ in range(n)]
color = ['white'] * n
distance = [-1] * n

for _ in range(n):
    adj = list(map(int, input().split()))
    i = adj[0]
    v = adj[2:]
    for j in v:
        adjMat[i - 1][j - 1] = 1

bfs(0)

for i in range(n):
    out = ''
    out += '{} {}'.format(i + 1, distance[i])
    print(out)

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import deque
n = int(input())
d = [-1] * (n + 1)
def bfs():
    d[1] = 0
    dq = deque([1])
    while len(dq) != 0:
        v = dq.popleft()
        for c in G[v]:
            if d[c] != -1 : continue
            d[c] = d[v] + 1
            dq.append(c)
    for i, x in enumerate(d[1:], start=1):
        print(i, x)
G = [0] + [list(map(int, inpput().split()[2:])) for i in range(n)]
bfs()

Submission status: Runtime Error

Solution code:
def srch(i, l, Lng, Dst):
    if Lng[i] > l:
        Lng[i] = l
        
    if Dst[i] is not None and len(Dst[i]) > 0:
        for c in Dst[i]:
            srch(c,l+1, Lng, Dst)

def main():
    num = int(input())
    Dst = [None for i in range(num + 1)]
    Lng = [999] * (num + 1)

    for n in range(1, num+1):
        a = list(map(int,input().split()))
        u = a[0]
        if a[1] > 0:
            Dst[u] = a[2:]

    srch(1, 0, Lng, Dst)

    for n in range(1, num+1):
        l = Lng[n]
        if l > num:
            l = -1
        print("{} {}".format(n,l))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = [[] for i in range(n)]

for i in range(n):
    v = list(map(int, input().split()))
    u = v[0] - 1
    for j in v[2:]:
        a[u].append(j-1)

d = [0] * n
isDiscovered = [False] * n

def bfs(x):
    global time_stamp
    isDiscovered [x] = True
    time_stamp += 1
    for i in a[x]:
        if not isDiscovered[i]:
            d[i] = d[x] + 1

bfs(0)
d_ = 1
while not(isDiscovered == [True] * n):
    for i in range(n):
        if d[i] is d_ and not isDiscovered[i]:
            bfs(i)
    d_ += 1

for i in range(n):
    print(i+1, d[i])

Submission status: Runtime Error

Solution code:
n = int(input())
a = [[] for i in range(n)]

for i in range(n):
    v = list(map(int, input().split()))
    u = v[0] - 1
    for j in v[2:]:
        a[u].append(j-1)

d = [0] * n
isDiscovered = [False] * n

def bfs(x):
    global time_stamp
    time_stamp += 1
    for i in a[x]:
        if not isDiscovered[i]:
            isDiscovered [i] = True
            d[i] = d[x] + 1

bfs(0)
d_ = 1
isDiscovered [0] = True
while not(isDiscovered == [True] * n):
    for i in range(n):
        if d[i] is d_ :
            bfs(i)
    d_ += 1

for i in range(n):
    print(i+1, d[i])

Submission status: Runtime Error

Solution code:
m = [[0 for _ in range(n+1)] for _ in range(n+1)]
mm = [[] for _ in range(n+1)]

n = int(input())
for _ in range(n):
	tmp = [int(x) for x in input().split()]
	u,k,l = tmp[0],tmp[1],tmp[2:]
	mm[u] += tmp[2:]
	for x in l:
		m[u][x] = 1
		
dp = [float('inf') for _ in range(n+1)]
queue = [1]

while queue:
	t = queue.pop(0)
	for x in mm[t]:
		if dp[x] > dp[t] + 1:
			dp[x] = dp[t] + 1
			queue.append(x)
		else:
			pass
			
for i,x in enumerate(queue):
	if i == 0:
		pass
	else:
		if x == float('inf'):
			print(i, -1)
		else:
			print(i, x)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
from Queue import Queue


def main():
    num = int(stdin.readline())

    L = []
    for _ in xrange(num):
        L.append([int(s) for s in stdin.readline().split()[2:]])

    d = [-1] * num
    d[0] = 0
    q = Queue()javascript:void(0)
    q.put(0)
    while not q.empty():
        u = q.get()
        for v in L[u]:
            if d[v-1] < 0:
                d[v-1] = d[u] + 1
                q.put(v-1)

    for i, v in enumerate(d):
        print(i+1, v)


main()

Submission status: WA: Presentation Error

Solution code:
def bfs(G, s):
    d = {key: -1 for key in G.keys()}
    d[s] = 0
    Q = [s]
    while len(Q) > 0:
        u = Q.pop(0)
        for v in G[u]:
            if d[v] < 0:
                d[v] = d[u] + 1
                Q.append(v)

    return d


if __name__ == '__main__':
    G = {}
    n = int(input())
    for _ in range(n):
        tmp = list(map(int, input().split()))
        u = tmp.pop(0)
        k = tmp.pop(0)
        G[u] = tmp
    d = bfs(G, 1)
    for node in G:
        print('{0} {1} '.format(node, d[node]))