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: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = []
    for i in range(n):
        e = LI()
        u = e[2:]
        for i in range(len(u)):
            u[i] -= 1
        v.append(u)
    d = [-1]*n
    d[0] = 0
    q = deque([0])
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if d[y] < 0:
                d[y] = nd
                q.append(y)
    for i in range(n):
        print(i+1,d[i])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n = int(input())
g = [input().split()[2:] for _ in range(n)]

from collections import deque
que = deque()
que.append(0)
d = [0] + [-1] * n

while que:
    u = que.popleft()

    for v in g[u]:
        v = int(v) - 1

        if d[v] < 0:
            d[v] = d[u] + 1
            que.append(v)

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

"""
・グラフの数を受け取る
・グラフを作る．今回は隣接リストで必要な部分だけを残してリスト化する
・キュー用の配列を作る（これはなんでもいい．普通のリストでも可）．そのキューには1番初めのスタート位置を入れておく
・最短距離を置いておくリストを用意
・queの中身がなくなるまで続ける
・queの中身を取り出して，それにくっついてるノードを全て舐めていく．int方で入力を受け取っていないから注意．1-indexを0-indexに変える．
・もしそこにまだBFSが訪れていなかったら，そこに前回の場所から1足した物を代入
・探索用のqueに追加しておく．追加しておくことでまたそのノードとつながってるところを調べることができる
・最後は出力．全てのノードの最短距離を出力
"""

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline

    from collections import deque, defaultdict
    from copy import deepcopy

    INFTY = -1   # 探索しなかったやつを-1としてprintしやすくするために-1とした。

    n = int(input())

    M = [[0]*n for _ in range(n)]

    def bfs(s):
        q = deque()
        q.append(s)
        d = [INFTY]*n
        d[s] = 0
        while q: # qが空だとwhileループから抜ける
            u = q.popleft()  # pythonのdequeはpopleft関数で戻り値がpopした要素になる
            for v in range(n):
                if M[u][v] == 0:
                    continue
                if d[v] != INFTY:
                    continue
                d[v] = d[u] + 1
                q.append(v)
        for i in range(n):
            print(str(i+1) + ' ' + str(d[i]))

    for _ in range(n):
        u, k, *vv = map(int, input().split())
        u -= 1
        for v in vv:
            v -= 1
            M[u][v] = 1

    bfs(0)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


N = int(input())
G = [[] for _ in range(N)]
for _ in range(N):
    ls = list(map(int, input().split()))
    u = ls[0] - 1
    for v in ls[2:]:
        G[u].append(v - 1)

dist = [-1] * N
que = deque([0])
dist[0] = 0

while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

for v in range(N):
    print("{} {}".format(v + 1, dist[v]))

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
g = [None] * n
visited = [0] * n
dist = [-1] * n
Q = deque()

while n:
    l = list(map(int, input().split()))
    g[l[0]-1] = [i-1 for i in l[2:]]
    n -= 1

Q.append((0, 0)) 
visited[0] = 1

while Q:
    i, d = Q.popleft()         
    dist[i] = d
    for c in g[i]:
        if not visited[c]:
            visited[c] = 1
            Q.append((c, d+1))

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

Submission status: Accepted

Solution code:
n = int(input())
d = [-1]*(n+1)
adjacent_list = [[] for _ in range(n+1)]
for _ in range(n):
    edge = list(map(int,input().split()))
    if len(edge) >= 3:
        adjacent_list[edge[0]].extend(edge[2:])

from collections import deque

que = deque()
que.append(1)
d[1] = 0
while len(que) != 0:
    v = que.popleft()
    for nv in adjacent_list[v]:
        if d[nv] == -1:
            d[nv] = d[v] + 1
        else:
            continue
        que.append(nv)

for i,dist in enumerate(d):
    if i == 0:
        continue
    print(i,dist)

Submission status: Accepted

Solution code:
n = int(input())
v = []
for i in range(n):
    v_i = list(map(int,input().split()))[2:]
    v.append(v_i)
    
d = [-1]*n
d[0]=0
queue = [1]
dis = 1
while len(queue)!=0:
    queue2 = []
    for i in queue:
        for nex in v[i-1]:
            if d[nex-1]==-1:
                d[nex-1]=dis
                queue2.append(nex)
    dis +=1
    queue = queue2

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

Submission status: Accepted

Solution code:
import sys
import queue
input = sys.stdin.readline
n = int(input())
g = [[] for _ in range(n+1)]
d = [-1 for _ in range(n+1)]
for _ in range(n):
    c = list(map(int,input().split()))
    g[c[0]] = c[2:]

depth = 0
q = queue.Queue()
p = queue.Queue()
q.put(1)
while not q.empty():
    while not q.empty():
        s = q.get()
        if d[s] < 0:
            d[s] = depth
            for i in g[s]:
                p.put(i)
    p, q = q, p
    depth += 1

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

Submission status: Accepted

Solution code:
import queue

n = int(input())
graph = {}
for _ in range(n):
  i = list(map(int,input().split()))
  graph[i[0]] = i[2:]

dist = [-1 for i in range(n)]
todo = queue.Queue()
seen = set()

dist[0] = 0
todo.put(1)

while (not todo.empty()):
  now = todo.get()
  for nx in graph[now]:
    if (dist[nx-1] != -1):
      continue
    dist[nx-1] = dist[now-1] + 1
    todo.put(nx)

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

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n = int(input())
    V = [None]*(n+1)
    ans = [None]*(n+1)
    for i in range(1, n+1):
        _, _, *v = map(int, input().split())
        V[i] = v
    q = deque([1])
    ans[1] = 0
    while q:
        node = q.pop()
        d = ans[node]+1
        for v in V[node]:
            if ans[v] is None:
                ans[v] = d
                q.appendleft(v)
    print(1, 0)
    for i, distance in enumerate(ans[2:], 2):
        print(i, distance or -1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

n = int(sys.stdin.readline().strip())
edges = [[] for _ in range(n)]
for _ in range(n):
    tmp = list(map(int, sys.stdin.readline().strip().split(" ")))
    for node in tmp[2:]:
        edges[tmp[0] - 1].append(node-1)
# print(edges)

distance = [0] * n
q = deque()
q.append((0, 0))
visited = set()
while q:
    node, d = q.popleft()
    # print(node, d)
    if node in visited:
        continue
    distance[node] = d
    visited.add(node)
    for next in edges[node]:
        # print("next", next)
        q.append((next, d + 1))

for i, d in enumerate(distance):
    if i == 0:
        print(1, 0)
    else:
        print(i + 1, d if d > 0 else -1)

Submission status: Accepted

Solution code:
import collections
n = int(input())
adj_list = []

for _ in range(n):
    adj = list(map(int, input().split(" ")))
    adj_list.append([c - 1 for c in adj[2:]])

distances = [-1 for _ in range(n)]
queue = collections.deque()
queue.append(0)
distances[0] = 0

while queue:
    p = queue.popleft()

    for next_p in adj_list[p]:
        if distances[next_p] == -1:
            distances[next_p] = distances[p] + 1
            queue.append(next_p)

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def bfs(graph, initial):
    n = len(graph) - 1
    dist = [-1] * (n + 1)
    q = deque([initial])
    visited = [False] * (n + 1)
    visited[initial] = True
    dist[initial] = 0

    while len(q) != 0:
        edge = q.popleft()
        nxt = graph[edge]

        for i, e in enumerate(nxt):
            if visited[e] is False:
                q.append(e)
                dist[e] = dist[edge] + 1
                visited[e] = True

    return dist


def main():
    N = I()
    graph = [[] for i in range(N+1)]

    for i in range(N):
        a = LI()
        edge = a[0]
        if a[1] == 0:
            continue
        for e in a[2:]:
            graph[edge].append(e)
            # graph[e].append(edge)

    # print(graph)
    ret = bfs(graph, 1)
    for i in range(1, N+1):
        print(i, ret[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
E = [[] for _ in range(N+1)]
for _ in range(N):
	tmp = list(map(int, input().split()))
	if tmp[1] == 0:
		continue
	E[tmp[0]] = tmp[2:]

cnt = [0 for _ in range(N+1)]
q = [1]

while q:
	cp = q.pop(0)
	for np in E[cp]:
		if cnt[np] != 0:
			continue
		
		cnt[np] = cnt[cp] + 1
		q.append(np)

for ind, cost in enumerate(cnt):
	if ind == 0:
		continue
	if ind == 1:
		print(ind, 0)
	else:
		if cost == 0:
			print(ind, -1)
		else:
			print(ind, cost)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
nodes = []
G ={}
is_visited = {}
q = deque()

for _ in range(N):
    lst = list(map(int, input().split()))
    idx = lst[0]
    nodes.append(idx)
    is_visited[idx] = False
    degree = lst[1]
    if degree > 0:
        G[idx] = lst[2:]
    else:
        G[idx] = []

INF = 10**12
costs = [INF]*N
# bfs
# 初期queue
que = deque()  # 必要なものはnodeidと原点からの距離
que.append(1)
costs[0] = 0
while que:
    node_id = que.popleft()  # 先入れ先出し
    cost = costs[node_id-1]
    for next_id in G[node_id]:
        if (costs[next_id-1] == INF):
            que.append(next_id)
            costs[next_id-1] = cost + 1
        
for i in range(N):
    if costs[i] != INF:
        print(i+1, costs[i])
    else:
        print(i+1, -1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# SimpleQueue でOKなのだが AOJ の環境では Python3.7 が使えない
from queue import Queue


class BFS():
    INFTY = sys.maxsize

    def __init__(self, M, n, debug=False):
        self.M = M
        self.n = n
        # 距離で訪問状態(color)を管理する
        self.d = [self.INFTY] * n
        self.debug = debug

    def bfs(self, s):
        q = Queue()
        q.put(s)
        self.d[s] = 0
        self.debug_print(q)

        while not q.empty():
            u = q.get()
            for v in range(self.n):
                if self.M[u][v] == 0:
                    continue
                if self.d[v] != self.INFTY:
                    continue
                self.d[v] = self.d[u] + 1
                q.put(v)
                self.debug_print(q)

        for i in range(self.n):
            if self.d[i] == self.INFTY:
                d = -1
            else:
                d = self.d[i]
            print(f'{i+1} {d}')

    def debug_print(self, q):
        if not self.debug:
            return
        print('d: ', self.d)
        print('q: ', q.queue)
        print('-------------------------')


def main():
    n = int(input())
    M = [[0] * n for _ in range(n)]

    for i in range(n):
        line = input()
        inputs = [int(x) for x in line.split(' ')]
        u = inputs.pop(0)
        u -= 1                  # 0 オリジンへ変換
        _ = inputs.pop(0)       # k （使わない...）
        for v in inputs:
            v -= 1              # 0 オリジンへ変換
            M[u][v] = 1

    BFS(M, n).bfs(0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
'''
所要時間は、分位であった。
'''


# ライブラリのインポート
#import re #正規表現
import sys
#import heapq
#import bisect
from collections import deque
#import math

def main():
    inf = 10000
    n = int(input())
    D = [inf for i in range(n)]
    L = [[] for i in range(n)]
    for i, line in enumerate(sys.stdin):
        L[i] = list(map(lambda x: int(x)-1, list(line.strip("\n").split())))

    q = deque([0])
    D[0] = 0
    while(len(q)):
        u = q.popleft()
        if L[u][1] == -1:
            continue
        for j in range(2,len(L[u])):
            if D[L[u][j]] == inf:
                q.append(L[u][j])
            D[L[u][j]] = min(D[L[u][0]] + 1, D[L[u][j]]) 

                      
    for i in range(n):
        print("{} {}".format(i+1,D[i])) if D[i] < inf else print("{} {}".format(i+1,-1))
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Myqueue():

    def __init__(self, size):
        self.size = size
        self.N = [None for _ in range(size)]
        self.head = 0
        self.tail = 0

    def is_empty(self):
        return self.head == self.tail

    def is_full(self):
        return self.head == (self.tail + 1) % self.size

    def enqueue(self, x):
        if self.is_full():
            raise OverflowError
        self.N[self.tail] = x
        self.tail += 1
        if self.tail == self.size:
            self.tail = 0

    def dequeue(self):
        if self.is_empty():
            raise IndexError
        x = self.N[self.head]
        self.head += 1
        if self.head == self.size:
            self.head = 0
        return x


class Node:

    def __init__(self):
        self.distance = -1
        self.status = 0

    def input_data(self, nodes):
        data = input().split()
        self.number = int(data[0])
        self.v = [nodes[int(x) - 1] for x in data[2:]]

n = int(input())
queue = Myqueue(n)
nodes = [Node() for _ in range(n)]
[node.input_data(nodes) for node in nodes]
nodes[0].status = 1
nodes[0].distance = 0
queue.enqueue(nodes[0])
while not queue.is_empty():
    u = queue.dequeue()
    for v in u.v: #type: Node
        if v.status == 0:
            v.status = 1
            v.distance = u.distance + 1
            queue.enqueue(v)
    u.status = 2


nodes.sort(key=lambda i: i.number)
for node in nodes:
    print(f"{node.number} {node.distance}")

Submission status: Accepted

Solution code:
from collections import deque

#キューを使った幅優先探索の実装
l = int(input())
rlist = []
for i in range(l):
    li = list(map(int, input().split()))
    rlist.append(deque([ll-1 for ll in li[2:]]))


color = ['white'] * l
queue = deque([])
d = [10000000] * l

def bfs(u):
    color[u] = 'gray'
    d[u] = 0
    queue.append(u)

    while(len(queue) > 0):
        u = queue.popleft()
        for rl in rlist[u]:
            if color[rl] == 'white':
                color[rl] = 'gray'
                d[rl] = d[u] + 1
                queue.append(rl)
        color[u] = 'black'

bfs(0)

for i in range(l):
    if d[i] == 10000000:
        d[i] = -1

for i in range(l):
    print(str(i+1) + ' ' + str(d[i]))

Submission status: Accepted

Solution code:
from collections import deque


def breadth_first_search(adj_matrix, n):
    distance = [0] + [-1] * (n - 1)
    searching = deque([0])
    while len(searching) > 0:
        start = searching.popleft()
        for end in range(n):
            if adj_matrix[start][end] and distance[end] == -1:
                searching.append(end)
                distance[end] = distance[start] + 1
    return distance


def main():
    n = int(input())
    adj = [[False for _ in range(n)] for _ in range(n)]
    for _ in range(n):
        ukv = input().split()
        id = int(ukv[0])
        dim = int(ukv[1])
        if dim > 0:
            nodes = map(int, ukv[2:])
            for node in nodes:
                adj[id - 1][node - 1] = True
    distance = breadth_first_search(adj, n)
    for i in range(n):
        print("{} {}".format(i + 1, distance[i]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

# データの入力
N = int(input())
DG = {}
for i in range(N):
    tmp = input().split()
    if int(tmp[1]) != 0:
        DG[i] = [int(x)-1 for x in tmp[2:]]
    else:
        DG[i] = []


result = {}
is_visited = {key: False for key in range(N)}
# bfs
# 初期queue
que = deque([(0, 0)])  # 必要なものはnodeidと原点からの距離
while que:
    nodeid, cost = que.popleft()  # 先入れ先出し
    result[nodeid] = cost
    is_visited[nodeid] = True  # この文は最初の1for目しか意味ないんだけどなんかうまい方法ないのか
    for nextnode in DG[nodeid]:
        if is_visited[nextnode]:
            pass
        else:  # 未訪問のものについては探索候補に入れる
            que.append((nextnode, cost + 1))
            is_visited[nextnode] = True  # 探索候補に入れた瞬間に訪問管理しないと重複を生じる場合がある

for i in range(N):
    if is_visited[i]:
        print(i + 1, result[i])
    else:
        print(i+1, -1)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
g = []
# ans = [[-1]*n for _ in range(n)]
ans = [-1] * n
done = set()
q = deque()

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

# print(g)

q.append(0)
# dis = 1
ans[0] = 0
done.add(1)

while q:
    idx = q.popleft()
    adj = g[idx]
    # print('node:', idx+1)

    for i in adj:
        if i not in done:
            ans[i-1] = ans[idx] + 1
            done.add(i)
            q.append(i-1)
    # if len(adj) > 0:
    #     dis += 1

# print(ans)

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

Submission status: Accepted

Solution code:
n=int(input())
a=[]
from collections import deque as dq
for i in range(n):
	aaa=list(map(int,input().split()))
	aa=aaa[2:]
	a.append(aa)
dis=[-1]*n
dis[0]=0
queue=dq([0])
while queue:
	p=queue.popleft()
	for i in range(len(a[p])):
		if dis[a[p][i]-1]==-1:
			queue.append(a[p][i]-1)
			dis[a[p][i]-1]=dis[p]+1
for i in range(n):
	print(i+1,dis[i])

Submission status: Accepted

Solution code:

import queue

WHITE = 0
GRAY = 1
BLACK = 2

NIL = -1
INF = 1000000000


def bfs(u):
    global Q
    Q.put(u)
    for i in range(n):
        d[i] = NIL
    d[u] = 0
    while not Q.empty():
        u = Q.get()
        for v in range(n):
            if (m[u][v] == 1) and (d[v] == NIL):
                d[v] = d[u] + 1
                Q.put(v)
n = int(input())

m = [[0 for i in range(n + 1)] for j in range(n + 1)]
vid = [0] * n
d = [0] * n
f = [0] * n
Q = queue.Queue()
color = [WHITE] * n
time = 0
nt = [0] * n

tmp = []
for i in range(n):
    nums=list(map(int,input().split()))
    tmp.append(nums)
    vid[i] = nums[0]

for i in range(n):
    for j in range(tmp[i][1]):
        m[i][vid.index(tmp[i][j + 2])] = 1

bfs(0)

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

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())
    graph = [[0 for i in range(n)] for _ in range(n)]
    frist = [0 for _ in range(n)]
    end = [0 for _ in range(n)]
    visit = [False for _ in range(n)]
    # get the group
    for i in range(n):
        datas = [int(num) for num in input().split(' ')]
        if datas[1] > 0:
            for j in datas[2:]:
                graph[datas[0] - 1][j - 1] = 1

    queue = [0]
    visit = [False for _ in range(n)]
    visit[0] = True
    depths = [0 for _ in range(n)]
    while len(queue) != 0:
        point = queue.pop(0)
        for i in range(n):
            if graph[point][i] == 1 and visit[i] is False:
                queue.append(i)
                visit[i] = True
                depths[i] = depths[point] + 1
        if len(queue) == 0:
            for i in range(n):
                if visit[i] is False:
                    queue.append(i)
                    depths[i] = -1
                    visit[i] = True

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

Submission status: Accepted

Solution code:
n=int(input())
ps=[0 for j in range(n+1)]

for i in range(n):
    p,d,*vs=[int(j) for j in input().split()]
    ps[p]=vs
    
dist=[-1 for i in range(n+1)]    
    
d=0
queue=[1]

while queue:
    pos=queue.pop(0)
    if dist[pos] == -1:
        dist[pos]=d
    for i in ps[pos]:
        if dist[i]==-1:
            queue.append(i)
            dist[i]=dist[pos]+1

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

Submission status: Accepted

Solution code:

def bfs(s):  # たぶんstartのs
    global n, M, color, d, q

    q.append(s)
    d[s] = 0

    while len(q) != 0:
        u = q.pop(0)

        for v in range(n):
            if M[u][v] != 1:
                continue

            if color[v] == 'WHITE':
                q.append(v)
                color[v] = 'GRAY'
                d[v] = d[u] + 1

        color[u] = 'BLACK'


n = int(input())

M = [[0 for i in range(n)] for j in range(n)]
color = ['WHITE'] * n  # 各頂点の色を記録。ホワイト（未探索）、グレイ（探索中）、ブラック（探索ずみ）
d = [-1] * n  # 始点0からvまでの距離
q = []

for i in range(n):
    _ = list(map(int, input().split()))
    u = _[0] - 1  # 0オリジンに変換

    degree = _[1]
    for j in range(degree):
        v = _[j+2] - 1  # 0オリジンに変換
        M[u][v] = 1

# for row in M:
#     print(' '.join(map(str, row)))

bfs(0)

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

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
E=[0]*n
for _ in range(n):
    u,k,*V=map(int,input().split())
    E[u-1]=V
d=[-1]*n
d[0]=0
todo=deque([1])
while todo:
    now=todo.popleft()
    for v in E[now-1]:
        if d[v-1]==-1:
            todo.append(v)
            d[v-1]=d[now-1]+1
for i in range(n):
    print(i+1,d[i])

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache(maxsize=None)
def solve(i, count):
    global ans
    global a
    if count >= N:
        return
    if ans[i][0] == -1:
        ans[i][0] = count
    elif ans[i][0] > count:
        ans[i][0] = count

    for x in range(a[i][1]):
        solve(a[i][2 + x] - 1, count + 1)


N = int(input())
a = []
for _ in range(N):
    a.append([int(x) for x in input().split()])

ans = [[-1 for i in range(1)] for j in range(N)]

solve(0, 0)

for i, x in enumerate(ans):
    print(i + 1, *x)

Submission status: Accepted

Solution code:
from collections import deque


def get_next_node(node, discovery_time, adj_mat):
    for i, node in enumerate(adj_mat[node]):
        if discovery_time[i] == 0 and node == 1:
            return i
    return None

def bfs(node, adj_mat):
    distances = [-1] * len(adj_mat)

    distances[node] = 0
    q = deque(maxlen=len(adj_mat))
    q.append(0)
    while q:
        visit_node = q.popleft()
        for j in range(len(adj_mat)):
            if adj_mat[visit_node][j] and distances[j]==-1:
                distances[j] = distances[visit_node] + 1
                q.append(j)
    
    for i, d in enumerate(distances):
        print(i+1, d)


if __name__ == "__main__":
    n_node = int(input())
    # f = open('alds1_11_c-input.txt', 'r')
    # n_node = int(f.readline())

    adjacency_mat = [[0 for i in range(n_node)] for j in range(n_node)]
    for i in range(n_node):
        command = list(map(int, input().split()))
        # command = list(map(int, f.readline().split()))

        i = command.pop(0) - 1
        n_edge = command.pop(0)

        for j in command:
            adjacency_mat[i][j-1] = 1

    # f.close()
    discovery_time = [0] * n_node
    finish_time = [0] * n_node
    bfs(0, adjacency_mat)

Submission status: Accepted

Solution code:
from collections import deque

N = 100
n = 0
M = None
WHITE = 0
GRAY = 1
BLACK = 2
INF = float('inf')
d = None


def main():
    global n, M, d
    M = [[0 for _ in range(N)] for _ in range(N)]
    n = int(input())
    d = [INF for _ in range(n)]

    for _ in range(n):
        u, k, *v_s = map(int, input().split(' '))
        for j in range(k):
            M[u-1][v_s[j-1]-1] = 1

    bfs()

    for i in range(n):
        print('{} {}'.format(i+1, d[i] if d[i] != INF else -1))


def bfs():
    q = deque()
    q.appendleft(0)
    d[0] = 0

    while len(q) > 0:
        u = q.pop()
        for v in range(n):
            if M[u][v] == WHITE:
                continue
            if d[v] != INF:
                continue
            d[v] = GRAY
            d[v] = d[u] + 1
            q.appendleft(v)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/11/ALDS1_11_C
# 実家のような安心感
# 与えられるノード番号についてはすべて0based indexに治す

from collections import deque

# データの入力
N = int(input())
DG = {}
for i in range(N):
    tmp = input().split()
    if int(tmp[1]) != 0:
        DG[i] = [int(x)-1 for x in tmp[2:]]
    else:
        DG[i] = []


result = {}
is_visited = {key: False for key in range(N)}
# bfs
# 初期queue
que = deque([(0, 0)])  # 必要なものはnodeidと原点からの距離
while que:
    nodeid, cost = que.popleft()  # 先入れ先出し
    result[nodeid] = cost
    is_visited[nodeid] = True  # この文は最初の1for目しか意味ないんだけどなんかうまい方法ないのか
    for nextnode in DG[nodeid]:
        if is_visited[nextnode]:
            pass
        else:  # 未訪問のものについては探索候補に入れる
            que.append((nextnode, cost + 1))
            is_visited[nextnode] = True  # 探索候補に入れた瞬間に訪問管理しないと重複を生じる場合がある

for i in range(N):
    if is_visited[i]:
        print(i + 1, result[i])
    else:
        print(i+1, -1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
from collections import deque

n=int(input())
G=[0]*n
memo=[0]*n
dis=[0]*n
dis[0]=1
que=deque()
que.append((0,1))

for i in range(n):
    inp=tuple(map(int,input().split()))
    G[inp[0]-1]=inp[2:]

while que:
    vertex,d=que.popleft()
    for v in G[vertex]:
        if not dis[v-1]:
            dis[v-1]=d+1
            que.append((v-1,d+1))
        

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
E = [None] * (N+1)
for _ in range(N):
    u, k, *vs = list(map(int, input().split()))
    E[u] = vs

d = [-1] * (N+1)
d[1] = 0
q = deque([(1, 0)])
while q:
    v, c = q.popleft()
    for u in E[v]:
        if d[u] < 0:
            d[u] = c+1
            q.append((u, c+1))

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

Submission status: Accepted

Solution code:
from typing import List
from collections import deque

def bfs(G: List[int], s: int) -> None:
	d[s] = 0
	color[s] = "GRAY"
	Q = deque()
	Q.append(s)
	while Q:
		u = Q.popleft()
		for v in G[u]:
			if color[v] == "WHITE":
				color[v] = "GRAY"
				d[v] = d[u] + 1
				pi[v] = u
				Q.append(v)
		color[u] = "BLACK"


if __name__ == "__main__":
	n = int(input())
	G = [[] for _ in range(n)]
	for _ in range(n):
		u, k, *adj = list(map(int, input().split()))
		u -= 1
		G[u] = [v - 1 for v in adj]
	color = ["WHITE" for _ in range(n)]
	d = [-1 for _ in range(n)]
	pi = [None for _ in range(n)]
	bfs(G, 0)
	for i in range(n):
		print(f"{i + 1} {d[i]}")

Submission status: Accepted

Solution code:
from collections import deque
from enum import Enum

class Color(Enum):
  WHITE = 0
  GRAY = 1
  BLACK = 2


N = int(input())
adj = [list(map(int, input().split()))[2:] for i in range(N)]


colors = [Color.WHITE for i in range(N)]
INF = N
d = [-1 for i in range(N)]
d[0] = 0

q = deque()
q.append(1)
colors[0] == Color.GRAY
while len(q) > 0:
  u = q.popleft()-1
  for v in adj[u]:
    v -= 1
    if colors[v] != Color.WHITE:
      continue
    d[v] = d[u] + 1
    colors[v] = Color.GRAY
    q.append(v+1)
  colors[u] = Color.BLACK

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

INF = 100100100

class Queue:
    __slots__ = ['Q', 'begin', 'end']
    def __init__(self):
        self.Q = [None] * 100
        self.begin = 0
        self.end = 0
    def full(self) -> bool:
        if self.begin == 0 and self.end == 99:
            return True
        elif self.begin == self.end + 1:
            return True
        else:
            return False
    def empty(self) -> bool:
        if self.begin == self.end:
            return True
        else:
            return False
    def insert(self, num: int):
        if self.full():
            print('Error: Queue is full.')
        else:
            if self.end == 99:
                self.end = 0
            else:
                self.end += 1
            self.Q[self.end-1] = num
    def pop(self) -> int:
        if self.empty():
            print('Error: Queue is empty.')
            return
        else:
            if self.begin == 99:
                self.begin = 0
                return self.Q[99]
            else:
                self.begin += 1
                return self.Q[self.begin-1]

def bfs(M: list, visited: list, d: list, v: int = 0):
    n = len(visited)
    Q = Queue()
    visited[v] = True
    d[v] = 0
    Q.insert(v)
    while not Q.empty():
        u = Q.pop()
        for i in range(n):
            if M[u][i] == 1 and not visited[i]:
                visited[i] = True
                d[i] = d[u] + 1
                Q.insert(i)


def main():
    n = int(input())
    M = [[0]*n for _ in range(n)]
    for _ in range(n):
        a = list(map(int, input().split()))
        i = a[0]-1
        for j in range(a[1]):
            k = a[j+2]-1
            M[i][k] = 1
    visited = [False] * n
    d = [INF] * n
    bfs(M, visited, d)
    for i, l in enumerate(d):
        if l == INF:
            print(i+1, -1)
        else:
            print(i+1, l)

if __name__ == '__main__': main()