# Graph I - Breadth First Search

Ԑ : 1 sec, : 131072 KB
pł͂

# DT

^ꂽLOt $G = (V, E)$ ɂāA_ $1$ e_ւ̍ŒZ $d$ipX̕ӂ̐̍ŏlj߂vO쐬ĂBe_ɂ $1$ $n$ ܂ł̔ԍӂĂ̂Ƃ܂B_ $1$ 炽ǂ蒅Ȃ_ɂẮAƂ-1 o͂ĂB

ŏ̍s $G$ ̒_ $n$ ^܂B $n$ sŊe_ $u$ ̗אڃXgȉ̌ŗ^܂F

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

$u$ ͒_̔ԍA$k$ $u$ ̏oA$v_1\; v_2\; ...\; v_k$@ $u$ ɗאڂ钸_̔ԍ܂B

• $1 \leq n \leq 100$

## o

e_ɂ $id$A$d$ Psɏo͂ĂB$id$ ͒_̔ԍA$d$ ͒_ $1$ 炻̒_܂ł̋܂B_ԍɏo͂ĂB

## ͗ 1

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


## o͗ 1

1 0
2 1
3 2
4 1
`

## Ql

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