Graph I - Graph

Ԑ : 1 sec, : 131072 KB
pł͂

Ot

Ot $G = (V, E)$ ̕\@ɂ͗אڃXg(adjacency list) ɂ\Ɨאڍs(adjacency matrices)ɂ\܂B

אڃXg\ł́A$V$ ̊e_ɑ΂ĂPAv $|V|$ ̃Xg $Adj[|V|]$ ŃOt\܂B_ $u$ ɑ΂āAאڃXg $Adj[u]$ $E$ ɑ $(u, v_i)$ ɂ邷ׂĂ̒_ $v_i$ ܂ł܂B܂A$Adj[u]$ $G$ ɂ $u$ Ɨאڂ邷ׂĂ̒_Ȃ܂B

Aאڍs\ł́A_ $i$ 璸_ $j$ ֕ӂꍇ $a_{ij}$ 1AȂꍇ 0 ł悤 $|V| \times |V|$ ̍s $A$ ŃOt\܂B

אڃXg\̌ŗ^ꂽLOt $G$ ̗אڍso͂vO쐬ĂB$G$ $n\; (=|V|)$ ̒_܂݁Aꂼ $1$ $n$ ܂ł̔ԍӂĂ̂Ƃ܂B

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

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

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

o

o͗ɏ]A$G$ ̗אڍso͂ĂB$a_{ij}$ ̊ԂɂP̋󔒂ĂB

• $1 \leq n \leq 100$

͗

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


o͗

0 1 0 1
0 0 0 1
0 0 0 0
0 0 1 0