(graph1.*)

Có hai cách tiêu chuẩn để biểu diễn một đồ thị, trong đó \(G\ = (V,E)\) là tập hợp các đỉnh \(V\) và \(E\) là tập hợp các cạnh; biểu diễn danh sách kề và biểu diễn ma trận kề.

Biểu diễn danh sách kề bao gồm một mảng \(Adj\lbrack|V|\rbrack\) các danh sách, mỗi danh sách cho mỗi đỉnh trong \(|V|\). Đối với mỗi \(u\), danh sách kề \(Adj\lbrack u\rbrack\) chứa tất cả các đỉnh \(v\) sao cho có một cạnh \((u,v) \in \ E\). Đó là, \(Adj\lbrack u\rbrack\) bao gồm tất cả các đỉnh kề với \(u\) trong \(G\).

Biểu diễn ma trận kề bao gồm ma trận \(|V| \times |V|\) sao cho \(a_{i,j} = 1\) nếu \((i,\ j) \in \ E\), \(a_{i,j}\ = 0\) nếu không.

Viết một chương trình đọc một đồ thị có hướng \(G\) được biểu diễn bởi danh sách kề, và in ra biểu diễn ma trận kề của nó. \(G\) bao gồm \(n\ ( = |V|)\) đỉnh được xác định bằng chỉ số \(1,2,...,n\) tương ứng.

Dữ liệu vào:

+ Dòng 1: chứa một số nguyên \(n\);

+ Tiếp theo là \(n\) dòng, dòng thứ \(i\) mô tả một danh sách các đỉnh kề với đỉnh \(i\) có dạng: \(u\ k\ v_{1}\ v_{2}\ ...\ v_{k}\) biểu thị danh sách gồm k đỉnh kề của đỉnh có chỉ số là \(u\).

Kết quả

+ Ghi ra biểu diễn ma trận kề của đồ thị đã cho.

Ví dụ: