Đề và Code môn Toán Rời Rạc 2 trên CodePTIT

Source: https://github.com/nvbangg/PTIT_Docs

CT001 - Chu trình Euler 01

(Tệp chương trình: CT.CPP; Thời gian chạy chương trình ≤ 1 giây)

Cho trước đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách cạnh. Yêu cầu:

(1) Kiểm tra G có phải là đồ thị Euler, nửa Euler hay không?
(2) Tìm một chu trình Euler bắt đầu tại đỉnh u của G là đồ thị Euler.

Dữ liệu: Vào từ tệp CT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Nếu t = 1 thì dòng thứ 2 chứa hai số nguyên dương n là số đỉnh và m là số cạnh của G, với n ≤ 100, m ≤ n(n-1)/2. Nếu t = 2 thì dòng thứ 2 chứa ba số nguyên dương n, m và u, trong đó n là số đỉnh, m là số cạnh và u là một đỉnh của G, với 1 ≤ u ≤ n ≤ 100, m ≤ n(n-1)/2.
Trong m dòng tiếp theo, mỗi dòng thứi (1 ≤ i ≤m) chứa chứa hai số nguyên u[i],v[i] là đỉnh đầu và đỉnh cuối của cạnh e[i], với 1 ≤ u[i] < v[i] ≤ n. Trong trường hợp t = 2 thì G là đồ thị Euler.

Kết quả: Ghi ra tệp CT.OUT:

Nếu t = 1 thì ghi ra giá trị 1 nếu G là Euler, giá trị 2 nếu G là nửa Euler và giá trị 0 nếu G không phải là Euler và nửa Euler.
Nếu t = 2 thì ghi ra trên một dòng gồm dãy các đỉnh mô tả chu trình Euler bắt đầu tại đỉnh u.

Ví dụ:

CT.in	CT.out	Giải thích
1 4 4 1 2 1 4 2 4 3 4	2	G là đồ thị nửa Euler
2 4 4 2 1 2 1 4 2 3 3 4	2 1 4 3 2	Chu trình Euler bắt đầu tại đỉnh u = 2 đi qua các cạnh theo thứ tự (2,1), (1,4), (4,3) và (3,2).

Giới hạn thời gian: 2s Giới hạn bộ nhớ: 65536 Kb

CT002 - Chu trình Euler 02

(Tệp chương trình: CT.CPP; Thời gian chạy chương trình ≤ 1 giây)

Cho trước đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu:

(1) Kiểm tra G có phải là đồ thị Euler, nửa Euler hay không?

(2) Tìm một chu trình Euler bắt đầu tại đỉnh u của G là đồ thị Euler.

Dữ liệu: Vào từ tệp CT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Nếu t = 1 thì dòng thứ hai chứa số nguyên dương n là số đỉnh của G, n  100. Nếu t = 2 thì dòng thứ 2 chứa hai số nguyên dương n và u, trong đó n là số đỉnh và u là một đỉnh của G, 1 ≤ u ≤ n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G. Trong trường hợp t = 2 thì G là đồ thị Euler.

Kết quả: Ghi ra tệp CT.OUT:

Nếu t = 1 thì ghi ra giá trị 1 nếu G là Euler, giá trị 2 nếu G là nửa Euler và giá trị 0 nếu G không phải là Euler và nửa Euler.
Nếu t = 2 thì ghi ra trên một dòng gồm dãy các đỉnh mô tả chu trình Euler bắt đầu tại đỉnh u.

Ví dụ:

CT.in	CT.out	Giải thích
1 4 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0	2	G là đồ thị nửa Euler
2 4 2 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0	2 1 4 3 2	Chu trình Euler bắt đầu tại đỉnh u = 2 đi qua các cạnh theo thứ tự (2,1), (1,4), (4,3) và (3,2).

Giới hạn thời gian: 2s Giới hạn bộ nhớ: 65536 Kb

CT003 - Chu trình Euler 03

(Tệp chương trình: CT.CPP; Thời gian chạy chương trình ≤ 1 giây)

Cho trước đồ thị có hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách kề.
Yêu cầu:
(1) Kiểm tra G có phải là đồ thị Euler, nửa Euler hay không?

(2) Tìm một chu trình Euler bắt đầu tại đỉnh u của G là đồ thị Euler.
Dữ liệu: Vào từ tệp CT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Nếu t = 1 thì dòng thứ hai chứa số nguyên dương n là số đỉnh của G, n ≤ 100. Nếu t = 2 thì dòng thứ 2 chứa hai số nguyên dương n và u, trong đó n là số đỉnh và u là một đỉnh của G, 1 ≤ u ≤ n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ n) chứa số tự nhiên k là số lương đỉnh kề với đỉnh i và k số tự nhiên theo thứ tự tăng v[1], ..., v[k] là số hiệu các đỉnh kề tương ứng. Trong trường hợp t = 2 thì G là đồ thị Euler.

Kết quả: Ghi ra tệp CT.OUT:

Nếu t = 1 thì ghi ra giá trị 1 nếu G là Euler, giá trị 2 nếu G là nửa Euler và giá trị 0 nếu G không phải là Euler và nửa Euler.
Nếu t = 2 thì ghi ra trên một dòng gồm dãy các đỉnh mô tả chu trình Euler bắt đầu tại đỉnh u.

Ví dụ:

CT.in	CT.out	Giải thích
1 4 2 2 4 1 4 1 1 1 3	2	G là đồ thị nửa Euler
2 4 3 1 2 1 3 1 4 1 1	3 4 1 2 3	Chu trình Euler bắt đầu tại đỉnh u = 3 đi qua các cạnh theo thứ tự (3,4), (4,1), (1,2) và (2,3).

Giới hạn thời gian: 2s Giới hạn bộ nhớ: 65536 Kb

CT004 - Chu trình Hamilton 01

(Tệp chương trình: CT.CPP; Thời gian chạy chương trình ≤ 1 giây)

Cho trước đồ thị G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề và một đỉnh u.

Yêu cầu: Tìm tất cả các chu trình Hamilton của G bắt đầu tại u.

Dữ liệu: Vào từ tệp CT.INP:

Dòng đầu chứa hai số nguyên dương n là số đỉnh và u là một đỉnh của G, 1 ≤ u ≤ n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp CT.OUT:

Dòng đầu ghi giá trị t là số lượng các chu trình Hamilton tìm được.
Trong trường hợp t > 0, tiếp theo ghi ra t dòng, mỗi dòng ghi dãy các đỉnh của một chu trình Hamilton.

Ví dụ:

CT.in	CT.out	Giải thích
4 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0	1 1 2 3 4 1	Chu trình Hamilton bắt đầu tại đỉnh u = 1 đi qua các cạnh theo thứ tự (1,2), (2,3), (3,4) và (4,1).
4 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0	0	Đồ thị không chứa chu trình Hamilton bắt đầu tại đỉnh u = 1.

Giới hạn thời gian: 2s Giới hạn bộ nhớ: 65536 Kb

CT005 - Chu trình Hamilton 02

(Tệp chương trình: CT.CPP; Thời gian chạy chương trình ≤ 1 giây)

Cho trước đồ thị có hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách cạnh và một đỉnh u.

Yêu cầu: Tìm tất cả các chu trình Hamilton của G bắt đầu tại u.

Dữ liệu: Vào từ tệp CT.INP:

Dòng đầu chứa ba số nguyên dương n, m và u, trong đó n là số đỉnh, m là số cạnh và u là một đỉnh của G, với 1 ≤u ≤ n ≤ 100, m ≤ n(n-1)/2.
Trong m dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤m) chứa hai số nguyên u[i],v[i] là đỉnh đầu và đỉnh cuối của cạnh e[i], với 1 ≤ u[i], v[i] ≤ n.

Kết quả: Ghi ra tệp CT.OUT:

Dòng đầu ghi giá trị t là số lượng các chu trình Hamilton tìm được.
Trong trường hợp t > 0, tiếp theo ghi ra t dòng, mỗi dòng ghi dãy các đỉnh của một chu trình Hamilton.

Ví dụ:

CT.in	CT.out	Giải thích
4 4 1 1 2 2 3 3 4 4 1	1 1 2 3 4 1	Chu trình Hamilton bắt đầu tại đỉnh u = 1 đi qua các cạnh theo thứ tự (1,2), (2,3), (3,4) và (4,1).
4 4 1 1 2 2 3 3 4 4 2	0	Đồ thị không chứa chu trình Hamilton bắt đầu tại đỉnh u = 1

Giới hạn thời gian: 2s Giới hạn bộ nhớ: 65536 Kb

CT006 - Chu trình Hamilton 03

(Tệp chương trình: CT.CPP; Thời gian chạy chương trình ≤ 1 giây)

Cho trước đồ thị có trọng số G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận trọng số không âm và một đỉnh u.

Yêu cầu: Tìm chu trình Hamilton của G bắt đầu tại u có tổng trọng số trên các cạnh là nhỏ nhất sử dụng thuật toán duyệt toàn thể.

Dữ liệu: Vào từ tệp CT.INP:

Dòng đầu chứa hai số nguyên dương n và u, trong đó n là số đỉnh, u là đỉnh của G, với 1 ≤ u ≤ n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng thứ i chứa n số tự nhiên c[i][j] mô tả ma trận trọng số của G. Trong đó, với hai đỉnh i, j (i khác j) có cạnh nối thì 0 < c[i][j] ≤ 50, nếu không có cạnh nối thì c[i][j] = 10000 và c[i][i] = 0.

Kết quả: Ghi ra tệp CT.OUT:

Nếu tìm được chu trình Hamilton thỏa mãn yêu cầu thì ghi ra theo quy cách:

Dòng đầu ghi tổng trọng số của tất cả các cạnh trong chu trình Hamilton tìm được;
Dòng sau ghi dãy các đỉnh trên chu trình Hamilton tìm được bắt đầu từ u.

Nếu không có chu trình Hamilton thì ghi giá trị 0.

Ví dụ:

CT.in	CT.out	Giải thích
5 1 0 31 25 23 10 16 0 2 7 12 3 3 0 25 54 15 2 33 0 50 16 15 32 3 0	20 1 5 4 2 3 1	Chu trình Hamilton bắt đầu tại u = 1 có tổng trọng số trên các cạnh là nhỏ nhất gồm các cạnh (1,5), (5,4), (4,2), (2,3) và (3,1) với tổng trọng số 20.
5 2 0 2 10000 10000 10000 2 0 3 1 10000 10000 3 0 4 5 10000 1 4 0 5 10000 10000 5 5 0	0	Không có chu trình Hamilton bắt đầu tại u = 2.

Giới hạn thời gian: 2s Giới hạn bộ nhớ: 65536 Kb

DT001 - Ma trận kề - Danh sách cạnh

Cho trước đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu:

(1) Xác định bậc các đỉnh của G;

(2) Biểu diễn G dưới dạng danh sách cạnh.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa số nguyên dương n không vượt quá 100 là số đỉnh của G.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra một dòng gồm n số tự nhiên tương ứng là bậc của n đỉnh.
Nếu t = 2 thì ghi ra theo qui cách:

Dòng đầu ghi ra hai số tự nhiên n và m là số đỉnh và số cạnh của G.
Trong m dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ m) ghi hai số u[i], v[i] là đỉnh đầu và đỉnh cuối của cạnh e[i]. Các cạnh của G được đánh số theo thứ tự từ điển.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0	2 2 1 1	Bậc của đỉnh 1 và 2 là 2, bậc của đỉnh 3 và 4 là 1.
2 4 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0	4 3 1 2 1 4 2 3	Đồ thị có 4 đỉnh và 3 cạnh là (1,2), (1,4), (2,3)

Giới hạn thời gian: 2s Giới hạn bộ nhớ: 65536 Kb

TRR1001 - 1.1 Đồ thị

Cho đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu:

(1) Xác định bậc các đỉnh của G;

(2) Biểu diễn G dưới dạng danh sách cạnh.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa số nguyên dương n không vượt quá 100 là số đỉnh của G.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra một dòng gồm n số tự nhiên tương ứng là bậc của n đỉnh.
Nếu t = 2 thì ghi ra theo qui cách:

Dòng đầu ghi ra hai số tự nhiên n và m là số đỉnh và số cạnh của G.
Trong m dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ m) ghi hai số u[i], v[i] là đỉnh đầu và đỉnh cuối của cạnh e[i]. Các cạnh của G được đánh số theo thứ tự từ điển.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0	2 2 1 1	Bậc của đỉnh 1 và 2 là 2, bậc của đỉnh 3 và 4 là 1.
2 4 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0	4 3 1 2 1 4 2 3	Đồ thị có 3 cạnh (1,2), (1,4) và (2,3).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1002 - 1.2 Đồ thị

Cho đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu:

(1) Xác định bậc các đỉnh của G;

(2) Biểu diễn G dưới dạng danh sách kề.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa số nguyên dương n không vượt quá 100 là số đỉnh của G.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra một dòng gồm n số tự nhiên tương ứng là bậc của n đỉnh.
Nếu t = 2 thì ghi ra theo qui cách:

Dòng đầu ghi ra số tự nhiên n là số đỉnh của G.
Trong n dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ n) ghi số tự nhiên k là số lương đỉnh kề với đỉnh i và k số tự nhiên theo thứ tự tăng v[1], …, v[k] là số hiệu các đỉnh kề tương ứng.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0	2 2 1 1	Bậc của đỉnh 1 và 2 là 2, bậc của đỉnh 3 và 4 là 1.
2 4 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0	4 2 2 4 2 1 3 1 2 1 1	Đỉnh 1 có 2 đỉnh kề là 2 và 4. Đỉnh 2 có 2 đỉnh kề là 1 và 3. Đỉnh 3 có 1 đỉnh kề là 2. Đỉnh 4 có 1 đỉnh kề là 1.

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1003 - 1.3 Đồ thị

Cho đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu:

(1) Xác định bậc các đỉnh của G;

(2) Biểu diễn G dưới dạng ma trận liên thuộc.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa số nguyên dương n không vượt quá 100 là số đỉnh của G.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra một dòng gồm n số tự nhiên tương ứng là bậc của n đỉnh.
Nếu t = 2 thì ghi ra n+1 dòng:

Dòng đầu ghi ra hai số tự nhiên n và m là số hàng và số cột của ma trận liên thuộc.
Trong n dòng tiếp theo, mỗi dòng ghi m số 0 hoặc 1 mô tả ma trận liên thuộc tìm được. Các cạnh của G được đánh số theo thứ tự từ điển.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0	2 2 1 1	Bậc của đỉnh 1 và 2 là 2, bậc của đỉnh 3 và 4 là 1.
2 4 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0	4 3 1 1 0 1 0 1 0 0 1 0 1 0	Đồ thị có 4 đỉnh và 3 cạnh (1,2), (1,4) và (2,3).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1004 - 1.4 Đồ thị

Cho đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách cạnh.

Yêu cầu:

(1) Xác định bậc các đỉnh của G;

(2) Biểu diễn G dưới dạng ma trận kề.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa hai số nguyên n là số đỉnh và m là số cạnh của G. Trong đó, 1 ≤ n ≤ 100 và 1 ≤ m ≤ n(n-1)/2.
Trong m dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ m) chứa hai số nguyên u[i], v[i] là đỉnh đầu và đỉnh cuối của cạnh e[i]. Trong đó, 1 ≤ u[i] < v[i] ≤ n.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra một dòng gồm n số tự nhiên tương ứng là bậc của n đỉnh.
Nếu t = 2 thì ghi ra n+1 dòng:

Dòng đầu ghi ra số tự nhiên n là bậc của ma trận kề.
Trong n dòng tiếp theo, mỗi dòng ghi n số 0 hoặc 1 mô tả ma trận kề tìm được.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 3 1 2 1 4 2 3	2 2 1 1	Bậc của đỉnh 1 và 2 là 2, bậc của đỉnh 3 và 4 là 1.
2 4 3 1 2 1 4 2 3	4 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0	Đồ thị có 4 đỉnh và 3 cạnh (1,2), (1,4) và (2,3).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1005 - 1.5 Đồ thị

Cho đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách cạnh.

Yêu cầu:

(1) Xác định bậc các đỉnh của G;

(2) Biểu diễn G dưới dạng danh sách kề.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa hai số nguyên n là số đỉnh và m là số cạnh của G. Trong đó, 1 ≤ n ≤ 100 và 1 ≤ m ≤ n(n-1)/2.
Trong m dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ m) chứa hai số nguyên u[i], v[i] là đỉnh đầu và đỉnh cuối của cạnh e[i]. Trong đó, 1 ≤ u[i] < v[i] ≤ n.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra một dòng gồm n số tự nhiên tương ứng là bậc của n đỉnh.
Nếu t = 2 thì ghi ra n+1 dòng:

Dòng đầu ghi ra số tự nhiên n là số đỉnh của G.
Trong n dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ n) ghi số tự nhiên k là số lương đỉnh kề với đỉnh i và k số tự nhiên theo thứ tự tăng v[1], …, v[k] là số hiệu các đỉnh kề tương ứng.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 3 1 2 1 4 2 3	2 2 1 1	Bậc của đỉnh 1 và 2 là 2, bậc của đỉnh 3 và 4 là 1.
2 4 3 1 2 1 4 2 3	4 2 2 4 2 1 3 1 2 1 1	Đỉnh 1 có 2 đỉnh kề là 2 và 4. Đỉnh 2 có 2 đỉnh kề là 1 và 3. Đỉnh 3 có 1 đỉnh kề là 2. Đỉnh 4 có 1 đỉnh kề là 1.

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1006 - 1.6 Đồ thị

Cho đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách cạnh.

Yêu cầu:

(1) Xác định bậc các đỉnh của G;

(2) Biểu diễn G dưới dạng ma trận liên thuộc.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa hai số nguyên n là số đỉnh và m là số cạnh của G. Trong đó, 1 ≤ n ≤ 100 và 1 ≤ m ≤ n(n-1)/2.
Trong m dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ m) chứa hai số nguyên u[i], v[i] là đỉnh đầu và đỉnh cuối của cạnh e[i]. Trong đó, 1 ≤ u[i] < v[i] ≤ n; Các cạnh của G được liệt kê theo thứ tự từ điển.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra một dòng gồm n số tự nhiên tương ứng là bậc của n đỉnh.
Nếu t = 2 thì ghi ra n+1 dòng:

Dòng đầu ghi ra hai số tự nhiên n và m là số hàng và số cột của ma trận liên thuộc.
Trong n dòng tiếp theo, mỗi dòng ghi m số 0 hoặc 1 mô tả ma trận liên thuộc tìm được. Các cạnh của G được đánh số theo thứ tự từ điển.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 3 1 2 1 4 2 3	2 2 1 1	Bậc của đỉnh 1 và 2 là 2, bậc của đỉnh 3 và 4 là 1.
2 4 3 1 2 1 4 2 3	4 3 1 1 0 1 0 1 0 0 1 0 1 0	Đồ thị có 4 đỉnh và 3 cạnh (1,2), (1,4) và (2,3).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1007 - 1.7 Đồ thị

Cho đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách kề.

Yêu cầu:

(1) Xác định bậc các đỉnh của G;

(2) Biểu diễn G dưới dạng ma trận kề.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa hai số nguyên n là số đỉnh của G. Trong đó, 1 ≤ n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ n) chứa số tự nhiên k là số lương đỉnh kề với đỉnh i và k số tự nhiên theo thứ tự tăng v[1], …, v[k] là số hiệu các đỉnh kề tương ứng.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra một dòng gồm n số tự nhiên tương ứng là bậc của n đỉnh.
Nếu t = 2 thì ghi ra n+1 dòng:

Dòng đầu ghi ra số tự nhiên n là bậc của ma trận kề.
Trong n dòng tiếp theo, mỗi dòng ghi n số 0 hoặc 1 mô tả ma trận kề tìm được.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 2 2 4 2 1 3 1 2 1 1	2 2 1 1	Bậc của đỉnh 1 và 2 là 2, bậc của đỉnh 3 và 4 là 1.
2 4 2 2 4 2 1 3 1 2 1 1	4 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0	Đồ thị có 4 đỉnh và 3 cạnh (1,2), (1,4) và (2,3).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1008 - 1.8 Đồ thị

Cho đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách kề.

Yêu cầu:

(1) Xác định bậc các đỉnh của G;

(2) Biểu diễn G dưới dạng danh sách cạnh.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa hai số nguyên n là số đỉnh của G. Trong đó, 1 ≤ n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ n) chứa số tự nhiên k là số lương đỉnh kề với đỉnh i và k số tự nhiên theo thứ tự tăng v[1], …, v[k] là số hiệu các đỉnh kề tương ứng.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra một dòng gồm n số tự nhiên tương ứng là bậc của n đỉnh.
Nếu t = 2 thì ghi ra theo qui cách:

Dòng đầu ghi ra hai số tự nhiên n và m là số đỉnh và số cạnh của G.
Trong m dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ m) ghi hai số u[i], v[i] là đỉnh đầu và đỉnh cuối của cạnh e[i]. Các cạnh của G được đánh số theo thứ tự từ điển

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 2 2 4 2 1 3 1 2 1 1	2 2 1 1	Bậc của đỉnh 1 và 2 là 2, bậc của đỉnh 3 và 4 là 1.
2 4 2 2 4 2 1 3 1 2 1 1	4 3 1 2 1 4 2 3	Đồ thị có 3 cạnh (1,2), (1,4) và (2,3).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1009 - 1.9 Đồ thị

Cho đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách kề.

Yêu cầu:

(1) Xác định bậc các đỉnh của G;

(2) Biểu diễn G dưới dạng ma trận liên thuộc.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa hai số nguyên n là số đỉnh của G. Trong đó, 1 ≤ n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ n) chứa số tự nhiên k là số lương đỉnh kề với đỉnh i và k số tự nhiên theo thứ tự tăng v[1], …, v[k] là số hiệu các đỉnh kề tương ứng.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra một dòng gồm n số tự nhiên tương ứng là bậc của n đỉnh.
Nếu t = 2 thì ghi ra n+1 dòng:

Dòng đầu ghi ra hai số tự nhiên n và m là số hàng và số cột của ma trận liên thuộc.
Trong n dòng tiếp theo, mỗi dòng ghi m số 0 hoặc 1 mô tả ma trận liên thuộc tìm được. Các cạnh của G được đánh số theo thứ tự từ điển.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 2 2 4 2 1 3 1 2 1 1	2 2 1 1	Bậc của đỉnh 1 và 2 là 2, bậc của đỉnh 3 và 4 là 1.
2 4 2 2 4 2 1 3 1 2 1 1	4 3 1 1 0 1 0 1 0 0 1 0 1 0	Đồ thị có 4 đỉnh và 3 cạnh (1,2), (1,4) và (2,3).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1010 - 1.10 Đồ thị

Cho đồ thị vô hướng có trọng số G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận trọng số.

Yêu cầu:

(1) Xác định bậc các đỉnh của G;

(2) Biểu diễn G dưới dạng danh sách cạnh với trọng số.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa số nguyên dương n không vượt quá 100 là số đỉnh của G.
Trong n dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ n) chứa n số tự nhiên c[i][j] (1 ≤ j ≤ n) mô tả ma trận trọng số của G. Trong đó, với hai đỉnh i, j (i khác j) có cạnh nối thì 0 < c[i][j] ≤ 50, nếu không có cạnh nối thì c[i][j] = 10000 và c[i][i] = 0.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra một dòng gồm n số tự nhiên tương ứng là bậc của n đỉnh.
Nếu t = 2 thì ghi ra theo qui cách:

Dòng đầu ghi ra hai số tự nhiên n và m là số đỉnh và số cạnh của G.
Trong m dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ m) ghi ba số u[i], v[i], w[i] là đỉnh đầu, đỉnh cuối và trọng số của cạnh e[i]. Các cạnh của G được đánh số theo thứ tự từ điển.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 0 1 10000 2 1 0 3 10000 10000 3 0 0 2 10000 0 0	2 2 1 1	Bậc của đỉnh 1 và 2 là 2, bậc của đỉnh 3 và 4 là 1.
2 4 0 1 10000 2 1 0 3 10000 10000 3 0 0 2 10000 0 0	4 3 1 2 1 1 4 2 2 3 3	Đồ thị có 3 cạnh (1,2), (1,4) và (2,3) với trọng số tương ứng là 1, 2, 3.

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1011 - 1.11 Đồ thị

Cho đồ thị vô hướng có trọng số G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách cạnh với trọng số.

Yêu cầu:

(1) Xác định bậc các đỉnh của G;

(2) Biểu diễn G dưới dạng ma trận trọng số.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa hai số nguyên dương n và m là số đỉnh và số cạnh của G, n ≤ 100 và 1 ≤ m ≤ n(n-1)/2.
Trong m dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ m) chứa ba số u[i], v[i], w[i] là đỉnh đầu, đỉnh cuối và trọng số của cạnh e[i]. Trong đó, 1 ≤ u[i] < v[i] ≤ n và 1 ≤ w[i] ≤ 50.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra một dòng gồm n số tự nhiên tương ứng là bậc của n đỉnh.
Nếu t = 2 thì ghi ra theo qui cách:

Dòng đầu ghi ra số tự nhiên n là số đỉnh của G.
Trong n dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ n) chứa n số tự nhiên c[i][j] (1 ≤ j ≤ n) mô tả ma trận trọng số của G. Trong đó, với hai đỉnh i, j (i khác j) có cạnh nối thì 0 < c[i][j] ≤ 50, nếu không có cạnh nối thì c[i][j] = 10000 và c[i][i] = 0.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 3 1 2 1 1 4 2 2 3 3	2 2 1 1	Bậc của đỉnh 1 và 2 là 2, bậc của đỉnh 3 và 4 là 1.
2 4 3 1 2 1 1 4 2 2 3 3	4 0 1 10000 2 1 0 3 10000 10000 3 0 10000 2 10000 10000 0	Đồ thị có 3 cạnh (1,2), (1,4) và (2,3) với trọng số tương ứng là 1, 2, 3.

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1012 - 1.12 Đồ thị

Cho đồ thị có hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu:

(1) Xác định bán bậc vào (deg-) và bán bậc ra (deg+) các đỉnh của G;

(2) Biểu diễn G dưới dạng danh sách cạnh.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa số nguyên dương n không vượt quá 100 là số đỉnh của G.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra n dòng, trong đó dòng thứ i (1 ≤ i ≤ n) ghi hai số tự nhiên deg- và deg+ tương ứng là bán bậc vào và ra của đỉnh i.
Nếu t = 2 thì ghi ra theo qui cách:

Dòng đầu ghi ra hai số tự nhiên n và m là số đỉnh và số cạnh của G.
Trong m dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ m) ghi hai số u[i], v[i] là đỉnh đầu và đỉnh cuối của cạnh e[i]. Các cạnh của G được đánh số theo thứ tự từ điển.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0	1 2 2 2 2 2 2 1	Có deg-(1) = 1, deg+(1) = 2; deg-(2) = deg+(2) = 2; deg-(3) = deg+(3) = 2; deg-(4) = 2, deg+(4) = 1.
2 4 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0	4 7 1 2 1 4 2 3 2 4 3 1 3 2 4 3	Đồ thị có 4 đỉnh và 7 cạnh (1,2), (1,4), (2,3), (2,4), (3,1), (3,2) và (4,3).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1013 - 1.13 Đồ thị

Cho đồ thị có hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu:

(1) Xác định bán bậc vào (deg-) và bán bậc ra (deg+) các đỉnh của G;

(2) Biểu diễn G dưới dạng danh sách kề.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa số nguyên dương n không vượt quá 100 là số đỉnh của G.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra n dòng, trong đó dòng thứ i (1 ≤ i ≤ n) ghi hai số tự nhiên deg- và deg+ tương ứng là bán bậc vào và ra của đỉnh i.
Nếu t = 2 thì ghi ra theo qui cách:

Dòng đầu ghi ra số tự nhiên n là số đỉnh của G.
Trong n dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ n) ghi số tự nhiên k là số lương đỉnh kề với đỉnh i và k số tự nhiên theo thứ tự tăng v[1], …, v[k] là số hiệu các đỉnh kề tương ứng.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0	1 2 2 2 2 2 2 1	Có deg-(1) = 1, deg+(1) = 2; deg-(2) = deg+(2) = 2; deg-(3) = deg+(3) = 2; deg-(4) = 2, deg+(4) = 1.
2 4 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0	4 2 2 4 2 3 4 2 1 2 1 3	Đỉnh 1 có 2 đỉnh kề là 2 và 4. Đỉnh 2 có 2 đỉnh kề là 3 và 34 Đỉnh 3 có 2 đỉnh kề là 1 và 2. Đỉnh 4 có 1 đỉnh kề là 3.

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1014 - 1.14 Đồ thị

Cho đồ thị có hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu:

(1) Xác định bán bậc vào (deg-) và bán bậc ra (deg+) các đỉnh của G;

(2) Biểu diễn G dưới dạng ma trận liên thuộc.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa số nguyên dương n không vượt quá 100 là số đỉnh của G.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra n dòng, trong đó dòng thứ i (1 ≤ i ≤ n) ghi hai số tự nhiên deg- và deg+ tương ứng là bán bậc vào và ra của đỉnh i.
Nếu t = 2 thì ghi ra n+1 dòng:

Dòng đầu ghi ra hai số tự nhiên n và m là số hàng và số cột của ma trận liên thuộc.
Trong n dòng tiếp theo, mỗi dòng ghi m số 0, 1 hoặc -1 mô tả ma trận liên thuộc tìm được. Các cạnh của G được đánh số theo thứ tự từ điển.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0	1 2 2 2 2 2 2 1	Có deg-(1) = 1, deg+(1) = 2; deg-(2) = deg+(2) = 2; deg-(3) = deg+(3) = 2; deg-(4) = 2, deg+(4) = 1.
2 4 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0	4 7 1 1 0 0 -1 0 0 -1 0 1 1 0 -1 0 0 0 -1 0 1 1 -1 0 -1 0 -1 0 0 1	Đồ thị có 7 cạnh (1,2), (1,4), (2,3), (2,4), (3,1), (3,2) và (4,3).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1015 - 1.15 Đồ thị

Cho đồ thị có hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách cạnh.

Yêu cầu:

(1) Xác định bán bậc vào (deg-) và bán bậc ra (deg+) các đỉnh của G;

(2) Biểu diễn G dưới dạng ma trận kề.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa hai số nguyên n là số đỉnh và m là số cạnh của G. Trong đó, 1 ≤ n ≤ 100 và 1 ≤ m ≤ n(n-1)/2.
Trong m dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ m) chứa hai số nguyên u[i], v[i] là đỉnh đầu và đỉnh cuối của cạnh e[i]. Trong đó, 1 ≤ u[i] < v[i] ≤ n.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra n dòng, trong đó dòng thứ i (1 ≤ i ≤ n) ghi hai số tự nhiên deg- và deg+ tương ứng là bán bậc vào và ra của đỉnh i.
Nếu t = 2 thì ghi ra n+1 dòng:

Dòng đầu ghi ra số tự nhiên n là bậc của ma trận kề.
Trong n dòng tiếp theo, mỗi dòng ghi n số 0 hoặc 1 mô tả ma trận kề tìm được

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 7 1 2 1 4 2 3 2 4 3 1 3 2 4 3	1 2 2 2 2 2 2 1	Có deg-(1) = 1, deg+(1) = 2; deg-(2) = deg+(2) = 2; deg-(3) = deg+(3) = 2; deg-(4) = 2, deg+(4) = 1.
2 4 7 1 2 1 4 2 3 2 4 3 1 3 2 4 3	4 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0	Đồ thị có 4 đỉnh và 7 cạnh (1,2), (1,4), (2,3), (2,4), (3,1), (3,2) và (4,3).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1016 - 1.16 Đồ thị

Cho đồ thị có hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách cạnh.

Yêu cầu:

(1) Xác định bán bậc vào (deg-) và bán bậc ra (deg+) các đỉnh của G;

(2) Biểu diễn G dưới dạng danh sách kề.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa hai số nguyên n là số đỉnh và m là số cạnh của G. Trong đó, 1 ≤ n ≤ 100 và 1 ≤ m ≤ n(n-1)/2.
Trong m dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ m) chứa hai số nguyên u[i], v[i] là đỉnh đầu và đỉnh cuối của cạnh e[i]. Trong đó, 1 ≤ u[i] < v[i] ≤ n.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra n dòng, trong đó dòng thứ i (1 ≤ i ≤ n) ghi hai số tự nhiên deg- và deg+ tương ứng là bán bậc vào và ra của đỉnh i.
Nếu t = 2 thì ghi ra n+1 dòng:

Dòng đầu ghi ra số tự nhiên n là số đỉnh của G.
Trong n dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ n) ghi số tự nhiên k là số lượng đỉnh kề với đỉnh i và k số tự nhiên theo thứ tự tăng v[1], …, v[k] là số hiệu các đỉnh kề tương ứng.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 7 1 2 1 4 2 3 2 4 3 1 3 2 4 3	1 2 2 2 2 2 2 1	Có deg-(1) = 1, deg+(1) = 2; deg-(2) = deg+(2) = 2; deg-(3) = deg+(3) = 2; deg-(4) = 2, deg+(4) = 1.
2 4 7 1 2 1 4 2 3 2 4 3 1 3 2 4 3	4 2 2 4 2 3 4 2 1 2 1 3	Đỉnh 1 có 2 đỉnh kề là 2 và 4. Đỉnh 2 có 2 đỉnh kề là 3 và 4. Đỉnh 3 có 2 đỉnh kề là 1 và 2. Đỉnh 4 có 1 đỉnh kề là 3.

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1017 - 1.17 Đồ thị

Cho đồ thị có hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách cạnh.

Yêu cầu:

(1) Xác định bán bậc vào (deg-) và bán bậc ra (deg+) các đỉnh của G;

(2) Biểu diễn G dưới dạng ma trận liên thuộc.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa hai số nguyên n là số đỉnh và m là số cạnh của G. Trong đó, 1 ≤ n ≤ 100 và 1 ≤ m ≤ n(n-1)/2.
Trong m dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ m) chứa hai số nguyên u[i], v[i] là đỉnh đầu và đỉnh cuối của cạnh e[i]. Trong đó, 1 ≤ u[i] < v[i] ≤ n.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra n dòng, trong đó dòng thứ i (1 ≤ i ≤ n) ghi hai số tự nhiên deg- và deg+ tương ứng là bán bậc vào và ra của đỉnh i.
Nếu t = 2 thì ghi ra n+1 dòng:

Dòng đầu ghi ra hai số tự nhiên n và m là số hàng và số cột của ma trận liên thuộc.
Trong n dòng tiếp theo, mỗi dòng ghi m số 0, 1 hoặc -1 mô tả ma trận liên thuộc tìm được. Các cạnh của G được đánh số theo thứ tự từ điển.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 7 1 2 1 4 2 3 2 4 3 1 3 2 4 3	1 2 2 2 2 2 2 1	Có deg-(1) = 1, deg+(1) = 2; deg-(2) = deg+(2) = 2; deg-(3) = deg+(3) = 2; deg-(4) = 2, deg+(4) = 1.
2 4 7 1 2 1 4 2 3 2 4 3 1 3 2 4 3	4 7 1 1 0 0 -1 0 0 -1 0 1 1 0 -1 0 0 0 -1 0 1 1 -1 0 -1 0 -1 0 0 1	Đồ thị có 4 đỉnh và 7 cạnh (1,2), (1,4), (2,3), (2,4), (3,1), (3,2) và (4,3).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1018 - 1.18 Đồ thị

Cho đồ thị có hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách kề.

Yêu cầu:

(1) Xác định bán bậc vào (deg-) và bán bậc ra (deg+) các đỉnh của G;;

(2) Biểu diễn G dưới dạng ma trận kề.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa hai số nguyên n là số đỉnh của G. Trong đó, 1 ≤ n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ n) chứa số tự nhiên k là số lương đỉnh kề với đỉnh i và k số tự nhiên theo thứ tự tăng v[1], …, v[k] là số hiệu các đỉnh kề tương ứng.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra n dòng, trong đó dòng thứ i (1 ≤ i ≤ n) ghi hai số tự nhiên deg- và deg+ tương ứng là bán bậc vào và ra của đỉnh i.
Nếu t = 2 thì ghi ra n+1 dòng:

Dòng đầu ghi ra số tự nhiên n là bậc của ma trận kề.
Trong n dòng tiếp theo, mỗi dòng ghi n số 0 hoặc 1 mô tả ma trận kề tìm được.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 2 2 4 2 3 4 2 1 2 1 3	1 2 2 2 2 2 2 1	Có deg-(1) = 1, deg+(1) = 2; deg-(2) = deg+(2) = 2; deg-(3) = deg+(3) = 2; deg-(4) = 2, deg+(4) = 1.
2 4 4 2 2 4 2 3 4 2 1 2 1 3	4 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0	Đồ thị có 4 đỉnh. Đỉnh 1 có 2 đỉnh kề là 2 và 4. Đỉnh 2 có 2 đỉnh kề là 3 và 34 Đỉnh 3 có 2 đỉnh kề là 1 và 2. Đỉnh 4 có 1 đỉnh kề là 3.

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1019 - 1.19 Đồ thị

Cho đồ thị có hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách kề.

Yêu cầu:

(1) Xác định bán bậc vào (deg-) và bán bậc ra (deg+) các đỉnh của G;;

(2) Biểu diễn G dưới dạng danh sách cạnh.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa số nguyên n là số đỉnh của G. Trong đó, 1 ≤ n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ n) chứa số tự nhiên k là số lương đỉnh kề với đỉnh i và k số tự nhiên theo thứ tự tăng v[1], …, v[k] là số hiệu các đỉnh kề tương ứng.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra n dòng, trong đó dòng thứ i (1 ≤ i ≤ n) ghi hai số tự nhiên deg- và deg+ tương ứng là bán bậc vào và ra của đỉnh i.
Nếu t = 2 thì ghi ra theo qui cách:

Dòng đầu ghi ra hai số tự nhiên n và m là số đỉnh và số cạnh của G.
Trong m dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ m) ghi hai số u[i], v[i] là đỉnh đầu và đỉnh cuối của cạnh e[i]. Các cạnh của G được đánh số theo thứ tự từ điển.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 2 2 4 2 3 4 2 1 2 1 3	1 2 2 2 2 2 2 1	Có deg-(1) = 1, deg+(1) = 2; deg-(2) = deg+(2) = 2; deg-(3) = deg+(3) = 2; deg-(4) = 2, deg+(4) = 1.
2 4 2 2 4 2 3 4 2 1 2 1 3	4 7 1 2 1 4 2 3 2 4 3 1 3 2 4 3	Đồ thị có 4 đỉnh và 7 cạnh (1,2), (1,4), (2,3), (2,4), (3,1), (3,2) và (4,3).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1020 - 1.20 Đồ thị

Cho đồ thị có hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách kề.

Yêu cầu:

(1) Xác định bán bậc vào (deg-) và bán bậc ra (deg+) các đỉnh của G;;

(2) Biểu diễn G dưới dạng ma trận liên thuộc.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa số nguyên n là số đỉnh của G. Trong đó, 1 ≤ n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ n) chứa số tự nhiên k là số lương đỉnh kề với đỉnh i và k số tự nhiên theo thứ tự tăng v[1], …, v[k] là số hiệu các đỉnh kề tương ứng.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra n dòng, trong đó dòng thứ i (1 ≤ i ≤ n) ghi hai số tự nhiên deg- và deg+ tương ứng là bán bậc vào và ra của đỉnh i.
Nếu t = 2 thì ghi ra n+1 dòng:

Dòng đầu ghi ra hai số tự nhiên n và m là số hàng và số cột của ma trận liên thuộc.
Trong n dòng tiếp theo, mỗi dòng ghi m số 0, 1 hoặc -1 mô tả ma trận liên thuộc tìm được. Các cạnh của G được đánh số theo thứ tự từ điển.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 2 2 4 2 3 4 2 1 2 1 3	1 2 2 2 2 2 2 1	Có deg-(1) = 1, deg+(1) = 2; deg-(2) = deg+(2) = 2; deg-(3) = deg+(3) = 2; deg-(4) = 2, deg+(4) = 1.
2 4 2 2 4 2 3 4 2 1 2 1 3	4 7 1 1 0 0 -1 0 0 -1 0 1 1 0 -1 0 0 0 -1 0 1 1 -1 0 -1 0 -1 0 0 1	Đồ thị có 4 đỉnh và 7 cạnh (1,2), (1,4), (2,3), (2,4), (3,1), (3,2) và (4,3).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1021 - 1.21 Đồ thị

Cho đồ thị có hướng có trọng số G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận trọng số.

Yêu cầu:

(1) Xác định bán bậc vào (deg-) và bán bậc ra (deg+) các đỉnh của G;

(2) Biểu diễn G dưới dạng danh sách cạnh với trọng số.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa số nguyên dương n không vượt quá 100 là số đỉnh của G.
Trong n dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ n) chứa n số tự nhiên c[i][j] (1 ≤ j ≤ n) mô tả ma trận trọng số của G. Trong đó, với hai đỉnh i, j (i khác j) có cạnh nối thì 0 < c[i][j] ≤ 50, nếu không có cạnh nối thì c[i][j] = 10000 và c[i][i] = 0.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra n dòng, trong đó dòng thứ i (1 ≤ i ≤ n) ghi hai số tự nhiên deg- và deg+ tương ứng là bán bậc vào và ra của đỉnh i.
Nếu t = 2 thì ghi ra theo qui cách:

Dòng đầu ghi ra hai số tự nhiên n và m là số đỉnh và số cạnh của G.
Trong m dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ m) ghi ba số u[i], v[i], w[i] là đỉnh đầu, đỉnh cuối và trọng số của cạnh e[i]. Các cạnh của G được đánh số theo thứ tự từ điển.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 0 1 10000 2 10000 0 3 4 5 6 0 10000 10000 10000 7 0	1 2 2 2 2 2 2 1	Có deg-(1) = 1, deg+(1) = 2; deg-(2) = deg+(2) = 2; deg-(3) = deg+(3) = 2; deg-(4) = 2, deg+(4) = 1.
2 4 0 1 10000 2 10000 0 3 4 5 6 0 10000 10000 10000 7 0	4 7 1 2 1 1 4 2 2 3 3 2 4 4 3 1 5 3 2 6 4 3 7	Đồ thị có 4 đỉnh và 7 cạnh (1,2), (1,4), (2,3), (2,4), (3,1), (3,2) và (4,3) với các trọng số tương ứng la 1, 2, 3, 4, 5, 6 và 7.

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR1022 - 1.22 Đồ thị

Cho đồ thị có hướng có trọng số G = (V, E) gồm n đỉnh biểu diễn dưới dạng danh sách cạnh với trọng số.

Yêu cầu:

(1) Xác định bán bậc vào (deg-) và bán bậc ra (deg+) các đỉnh của G;

(2) Biểu diễn G dưới dạng ma trận trọng số.

Dữ liệu: Vào từ tệp DT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa hai số nguyên dương n và m là số đỉnh và số cạnh của G, n ≤ 100 và 1 ≤ m ≤ n(n-1)/2.
Trong m dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ m) chứa ba số u[i], v[i], w[i] là đỉnh đầu, đỉnh cuối và trọng số của cạnh e[i]. Trong đó, 1 ≤ u[i] < v[i] ≤ n và 1 ≤ w[i] ≤ 50.

Kết quả: Ghi ra tệp DT.OUT:

Nếu t = 1 thì ghi ra n dòng, trong đó dòng thứ i (1 ≤ i ≤ n) ghi hai số tự nhiên deg- và deg+ tương ứng là bán bậc vào và ra của đỉnh i.
Nếu t = 2 thì ghi ra theo qui cách:

Dòng đầu ghi ra số tự nhiên n là số đỉnh của G.
Trong n dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ n) chứa n số tự nhiên c[i][j] (1 ≤ j ≤ n) mô tả ma trận trọng số của G. Trong đó, với hai đỉnh i, j (i khác j) có cạnh nối thì 0 < c[i][j] ≤ 50, nếu không có cạnh nối thì c[i][j] = 10000 và c[i][i] = 0.

Ví dụ:

DT.INP	DT.OUT	Giải thích
1 4 7 1 2 1 1 4 2 2 3 3 2 4 4 3 1 5 3 2 6 4 3 7	1 2 2 2 2 2 2 1	Có deg-(1) = 1, deg+(1) = 2; deg-(2) = deg+(2) = 2; deg-(3) = deg+(3) = 2; deg-(4) = 2, deg+(4) = 1.
2 4 7 1 2 1 1 4 2 2 3 3 2 4 4 3 1 5 3 2 6 4 3 7	4 0 1 10000 2 10000 0 3 4 5 6 0 10000 10000 10000 7 0	Đồ thị có 4 đỉnh và 7 cạnh (1,2), (1,4), (2,3), (2,4), (3,1), (3,2) và (4,3) với các trọng số tương ứng la 1, 2, 3, 4, 5, 6 và 7.

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR2001 - 2.1 Đường đi

Cho trước đồ thị G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề và hai đỉnh u, v.

Yêu cầu:

(1) Tìm số lượng đường đi độ dài 2 trên G từ đỉnh u đến v.

(2) Tìm đường đi trên G từ đỉnh u đến v sử dụng thuật toán tìm kiếm theo chiều sâu (DFS).

Dữ liệu: Vào từ tệp TK.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa ba số nguyên dương n, u và v. Trong đó, n là số đỉnh của G, u và v là hai đỉnh của G, với 1 ≤ u, v ≤ n ≤ 100 và u khác v.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp TK.OUT:

Nếu t = 1 thì ghi ra giá trị là số lượng đường đi độ dài 2 trên G từ đỉnh u đến v.
Nếu t = 2 thì ghi ra trên một dòng gồm dãy các đỉnh mô tả đường đi trên G từ u đến v. Trong trường hợp không có đường đi trên G từ u đến v thì ghi số 0.

Ví dụ:

TK.INP	TK.OUT	Giải thích
1 4 2 4 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0	2	Có 2 đường đi độ dài 2 trên G từ đỉnh 2 đến 4 theo các cạnh là (2,1), (1,4) và (2,3), (3,4).
2 4 1 4 0 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0	1 3 2 4	Đường đi từ đỉnh 1 đến đỉnh 4 tìm được theo DFS qua các cạnh theo thứ tự (1,3), (3,2) và (2,4).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR2002 - 2.2 Đường đi

Cho trước đồ thị G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề và hai đỉnh u, v.

Yêu cầu:

(1) Tìm số lượng đường đi độ dài 2 trên G từ đỉnh u đến v.

(2) Tìm đường đi trên G từ đỉnh u đến v sử dụng thuật toán tìm kiếm theo chiều rộng (BFS).

Dữ liệu: Vào từ tệp TK.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Dòng thứ hai chứa ba số nguyên dương n, u và v. Trong đó, n là số đỉnh của G, u và v là hai đỉnh của G, với 1 ≤ u, v ≤ n ≤ 100 và u khác v.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp TK.OUT:

Nếu t = 1 thì ghi ra giá trị là số lượng đường đi độ dài 2 trên G từ đỉnh u đến v.
Nếu t = 2 thì ghi ra trên một dòng gồm dãy các đỉnh mô tả đường đi trên G từ u đến v. Trong trường hợp không có đường đi trên G từ u đến v thì ghi số 0.

Ví dụ:

TK.INP	TK.OUT	Giải thích
1 4 2 4 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0	2	Có 2 đường đi độ dài 2 trên G từ đỉnh 2 đến 4 theo các cạnh là (2,1), (1,4) và (2,3), (3,4).
2 4 1 4 0 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0	1 3 4	Đường đi từ đỉnh 1 đến đỉnh 4 tìm được theo BFS qua các cạnh theo thứ tự (1,3) và (3,4).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR2009 - 2.9 Liên thông

Cho trước đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu: Tìm các thành phần liên thông của G sử dụng thuật toán tìm kiếm theo chiều sâu (DFS).

Dữ liệu: Vào từ tệp TK.INP:

Dòng đầu chứa số nguyên dương n là số đỉnh của G, n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp TK.OUT:

Dòng đầu ghi ra giá trị lt là số lượng các thành phần liên thông của G.
Trong lt dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ lt) ghi các đỉnh thuộc thành phần liên thông thứ i theo thứ tự tăng.

Ví dụ:

TK.INP	TK.OUT	Giải thích
5 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0	2 1 2 3 4 5	Đồ thị có hai thành phần liên thông. Thành phần liên thông thứ 1 gồm các đỉnh 1, 2 và 3. Thành phần liên thông thứ 2 gồm các đỉnh 4 và 5.

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR2012 - 2.12 Liên thông

Cho trước đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu: Tìm các thành phần liên thông của G sử dụng thuật toán tìm kiếm theo chiều rộng (BFS).

Dữ liệu: Vào từ tệp TK.INP:

Dòng đầu chứa số nguyên dương n là số đỉnh của G, n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp TK.OUT:

Dòng đầu ghi ra giá trị lt là số lượng các thành phần liên thông của G.
Trong lt dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ lt) ghi các đỉnh thuộc thành phần liên thông thứ i theo thứ tự tăng.

Ví dụ:

TK.INP	TK.OUT	Giải thích
5 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0	2 1 2 3 4 5	Đồ thị có 2 thành phần liên thông. Thành phần liên thông thứ 1 gồm các đỉnh 1, 2 và 3. Thành phần liên thông thứ 2 gồm các đỉnh 4 và 5.

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR2015 - 2.15 Liên thông

Cho trước đồ thị có hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu: Xác định tính liên thông của G sử dụng thuật toán tìm kiếm theo chiều sâu (DFS).

Dữ liệu: Vào từ tệp TK.INP:

Dòng đầu chứa số nguyên dương n là số đỉnh của G, n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp TK.OUT theo quy cách :

Ghi ra giá trị 1 nếu G liên thông mạnh.
Ghi ra giá trị 2 nếu G liên thông không liên thông mạnh nhưng liên thông yếu.
Ghi ra giá trị 0 nếu G liên thông không liên thông mạnh và không liên thông yếu.

Ví dụ:

TK.INP	TK.OUT	Giải thích
4 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0	1	Đồ thị liên thông mạnh.
4 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0	2	Đồ thị không liên thông mạnh nhưng liên thông yếu.

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR2018 - 2.18 Liên thông

[Lỗi khi tải nội dung]

TRR2021 - 2.21 Đỉnh trụ

Cho trước đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu: Tìm các đỉnh trụ của G sử dụng thuật toán tìm kiếm theo chiều sâu (DFS).

Dữ liệu: Vào từ tệp TK.INP:

Dòng đầu chứa số nguyên dương n là số đỉnh của G, n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp TK.OUT:

Dòng đầu ghi ra giá trị t là số lượng các đỉnh trụ của G.
Trong trường hợp t > 0, dòng tiếp theo ghi các đỉnh trụ tìm được theo thứ tự tăng.

Ví dụ:

TK.INP	TK.OUT	Giải thích
5 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0	2 2 3	Đồ thị có hai đỉnh trụ là 2 và 3.

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR2024 - 2.24 Đỉnh trụ

Cho trước đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu: Tìm các đỉnh trụ của G sử dụng thuật toán tìm kiếm theo chiều rộng (BFS).

Dữ liệu: Vào từ tệp TK.INP:

Dòng đầu chứa số nguyên dương n là số đỉnh của G, n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp TK.OUT:

Dòng đầu ghi ra giá trị t là số lượng các đỉnh trụ của G.
Trong trường hợp t > 0, dòng tiếp theo ghi các đỉnh trụ tìm được theo thứ tự tăng.

Ví dụ:

TK.INP	TK.OUT	Giải thích
5 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0	2 2 3	Đồ thị có hai đỉnh trụ là 2 và 3.

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR2027 - 2.27 Cạnh cầu

Cho trước đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu: Tìm các cạnh cầu của G sử dụng thuật toán tìm kiếm theo chiều sâu (DFS).

Dữ liệu: Vào từ tệp TK.INP:

Dòng đầu chứa số nguyên dương n là số đỉnh của G, n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp TK.OUT:

Dòng đầu ghi ra giá trị c là số lượng các cạnh cầu của G.
Trong trường hợp c > 0, trong c dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ c) ghi hai số nguyên dương u[i] và v[i] là đỉnh đầu và đỉnh cuối của cạnh cầu thứ i tìm được. Các cạnh cầu được ghi ra theo thứ tự từ điển.

Ví dụ:

TK.INP	TK.OUT	Giải thích
5 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0	2 1 2 2 3	Đồ thị có hai cạnh cầu là (1,2) và (2,3).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR2030 - 2.30 Cạnh cầu

Cho trước đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu: Tìm các cạnh cầu của G sử dụng thuật toán tìm kiếm theo chiều rộng (BFS).

Dữ liệu: Vào từ tệp TK.INP:

Dòng đầu chứa số nguyên dương n là số đỉnh của G, n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp TK.OUT:

Dòng đầu ghi ra giá trị c là số lượng các cạnh cầu của G.
Trong trường hợp c > 0, trong c dòng tiếp theo, mỗi dòng thứ i (1 ≤ i ≤ c) ghi hai số nguyên dương u[i] và v[i] là đỉnh đầu và đỉnh cuối của cạnh cầu thứ i tìm được. Các cạnh cầu được ghi ra theo thứ tự từ điển.

Ví dụ:

TK.INP	TK.OUT	Giải thích
5 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0	2 1 2 2 3	Đồ thị có hai cạnh cầu là (1,2) và (2,3).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR3001 - 3.1 Chu trình Euler

Cho trước đồ thị vô hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu:

(1) Kiểm tra G có phải là đồ thị Euler, nửa Euler hay không?

(2) Tìm một chu trình Euler bắt đầu tại đỉnh u của G là đồ thị Euler.

Dữ liệu: Vào từ tệp CT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Nếu t = 1 thì dòng thứ hai chứa số nguyên dương n là số đỉnh của G, n ≤ 100. Nếu t = 2 thì dòng thứ 2 chứa hai số nguyên dương n và u, trong đó n là số đỉnh và u là một đỉnh của G, 1 ≤ u ≤ n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G. Trong trường hợp t = 2 thì G là đồ thị Euler.

Kết quả: Ghi ra tệp CT.OUT:

Nếu t = 1 thì ghi ra giá trị 1 nếu G là Euler, giá trị 2 nếu G là nửa Euler và giá trị 0 nếu G không phải là Euler và nửa Euler.
Nếu t = 2 thì ghi ra trên một dòng gồm dãy các đỉnh mô tả chu trình Euler bắt đầu tại đỉnh u.

Ví dụ:

CT.INP	CT.OUT	Giải thích
1 4 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0	2	Đồ thị G là nửa Euler.
2 4 2 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0	2 1 4 3 2	Chu trình Euler bắt đầu tại đỉnh u = 2 đi qua các cạnh theo thứ tự (2,1), (1,4), (4,3) và (3,2).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR3004 - 3.4 Chu trình Euler

Cho trước đồ thị có hướng G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề.

Yêu cầu:

(1) Kiểm tra G có phải là đồ thị Euler, nửa Euler hay không?

(2) Tìm một chu trình Euler bắt đầu tại đỉnh u của G là đồ thị Euler.

Dữ liệu: Vào từ tệp CT.INP:

Dòng đầu chứa số nguyên dương t nhận giá trị 1 hoặc 2.
Nếu t = 1 thì dòng thứ hai chứa số nguyên dương n là số đỉnh của G, n ≤ 100. Nếu t = 2 thì dòng thứ 2 chứa hai số nguyên dương n và u, trong đó n là số đỉnh và u là một đỉnh của G, 1 ≤ u ≤ n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G. Trong trường hợp t = 2 thì G là đồ thị Euler.

Kết quả: Ghi ra tệp CT.OUT:

Nếu t = 1 thì ghi ra giá trị 1 nếu G là Euler, giá trị 2 nếu G là nửa Euler và giá trị 0 nếu G không phải là Euler và nửa Euler.
Nếu t = 2 thì ghi ra trên một dòng gồm dãy các đỉnh mô tả chu trình Euler bắt đầu tại đỉnh u.

Ví dụ:

CT.INP	CT.OUT	Giải thích
1 4 0 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0	2	Đồ thị G là nửa Euler.
2 4 3 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0	3 4 1 2 3	Chu trình Euler bắt đầu tại đỉnh u = 3 đi qua các cạnh theo thứ tự (3,4), (4,1), (1,2) và (2,3).

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

TRR3007 - 3.7 Chu trình Hamilton

Cho trước đồ thị G = (V, E) gồm n đỉnh biểu diễn dưới dạng ma trận kề và một đỉnh u.

Yêu cầu: Tìm tất cả các chu trình Hamilton của G bắt đầu tại u.

Dữ liệu: Vào từ tệp CT.INP:

Dòng đầu chứa hai số nguyên dương n là số đỉnh và u là một đỉnh của G, 1 ≤ u ≤ n ≤ 100.
Trong n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 mô tả ma trận kề của G.

Kết quả: Ghi ra tệp CT.OUT:

Nếu không tìm được chu trình Hamilton thì ghi ra giá trị 0.
Trong trường hợp tìm được chu trình Hamilton thì mỗi dòng ghi dãy các đỉnh của một chu trình Hamilton. Dòng cuối cùng ghi giá trị t là số lượng các chu trình Hamilton tìm được.

Ví dụ:

CT.INP	CT.OUT	Giải thích
4 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0	1 2 3 4 1 1	Chu trình Hamilton bắt đầu tại đỉnh u = 1 đi qua các cạnh theo thứ tự (1,2), (2,3), (3,4) và (4,1).
4 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0	0	Đồ thị không chứa chu trình Hamilton bắt đầu tại đỉnh u = 1.

Giới hạn thời gian: 1s Giới hạn bộ nhớ: 65536 Kb

Name		Name	Last commit message	Last commit date
solve		solve
CT001_ChuTrinhEuler01.cpp		CT001_ChuTrinhEuler01.cpp
CT002_ChuTrinhEuler02.cpp		CT002_ChuTrinhEuler02.cpp
CT003_AC.cpp		CT003_AC.cpp
CT003_ChuTrinhEuler03.cpp		CT003_ChuTrinhEuler03.cpp
CT004_ChuTrinhHamilton01.cpp		CT004_ChuTrinhHamilton01.cpp
CT005_ChuTrinhHamilton02.cpp		CT005_ChuTrinhHamilton02.cpp
CT006_ChuTrinhHamilton03.cpp		CT006_ChuTrinhHamilton03.cpp
DT001_MaTranKe-DanhSachCanh.cpp		DT001_MaTranKe-DanhSachCanh.cpp
README.md		README.md
TRR1001_1.1DoThi.cpp		TRR1001_1.1DoThi.cpp
TRR1002_1.2DoThi.cpp		TRR1002_1.2DoThi.cpp
TRR1003_1.3DoThi.cpp		TRR1003_1.3DoThi.cpp
TRR1004_1.4DoThi.cpp		TRR1004_1.4DoThi.cpp
TRR1005_1.5DoThi.cpp		TRR1005_1.5DoThi.cpp
TRR1006_1.6DoThi.cpp		TRR1006_1.6DoThi.cpp
TRR1007_1.7DoThi.cpp		TRR1007_1.7DoThi.cpp
TRR1008_1.8DoThi.cpp		TRR1008_1.8DoThi.cpp
TRR1009_1.9DoThi.cpp		TRR1009_1.9DoThi.cpp
TRR1010_1.10DoThi.cpp		TRR1010_1.10DoThi.cpp
TRR1011_1.11DoThi.cpp		TRR1011_1.11DoThi.cpp
TRR1012_1.12DoThi.cpp		TRR1012_1.12DoThi.cpp
TRR1013_1.13DoThi.cpp		TRR1013_1.13DoThi.cpp
TRR1014_1.14DoThi.cpp		TRR1014_1.14DoThi.cpp
TRR1015_1.15DoThi.cpp		TRR1015_1.15DoThi.cpp
TRR1016_1.16DoThi.cpp		TRR1016_1.16DoThi.cpp
TRR1017_1.17DoThi.cpp		TRR1017_1.17DoThi.cpp
TRR1018_1.18DoThi.cpp		TRR1018_1.18DoThi.cpp
TRR1019_1.19DoThi.cpp		TRR1019_1.19DoThi.cpp
TRR1020_1.20DoThi.cpp		TRR1020_1.20DoThi.cpp
TRR1021_1.21DoThi.cpp		TRR1021_1.21DoThi.cpp
TRR1022_1.22DoThi.cpp		TRR1022_1.22DoThi.cpp
TRR2001_2.1DuongDi.cpp		TRR2001_2.1DuongDi.cpp
TRR2002_2.2DuongDi.cpp		TRR2002_2.2DuongDi.cpp
TRR2009_2.9LienThong.cpp		TRR2009_2.9LienThong.cpp
TRR2012_2.12LienThong.cpp		TRR2012_2.12LienThong.cpp
TRR2015_2.15LienThong.cpp		TRR2015_2.15LienThong.cpp
TRR2021_2.21DinhTru.cpp		TRR2021_2.21DinhTru.cpp
TRR2024_2.24DinhTru.cpp		TRR2024_2.24DinhTru.cpp
TRR2027_2.27CanhCau.cpp		TRR2027_2.27CanhCau.cpp
TRR2030_2.30CanhCau.cpp		TRR2030_2.30CanhCau.cpp
TRR3001_3.1ChuTrinhEuler.cpp		TRR3001_3.1ChuTrinhEuler.cpp
TRR3004_3.4ChuTrinhEuler.cpp		TRR3004_3.4ChuTrinhEuler.cpp
TRR3007_3.7ChuTrinhHamilton.cpp		TRR3007_3.7ChuTrinhHamilton.cpp
TRR4001_4.1CayKhung.cpp		TRR4001_4.1CayKhung.cpp
TRR4004_4.4CayKhung.cpp		TRR4004_4.4CayKhung.cpp
TRR4007_4.7CayKhung.cpp		TRR4007_4.7CayKhung.cpp
TRR5001_5.1DuongDiNganNhat.cpp		TRR5001_5.1DuongDiNganNhat.cpp

Latest commit

History

Folders and files

Repository files navigation

Đề và Code môn Toán Rời Rạc 2 trên CodePTIT

Source: https://github.com/nvbangg/PTIT_Docs

CT001 - Chu trình Euler 01

CT002 - Chu trình Euler 02

CT003 - Chu trình Euler 03

CT004 - Chu trình Hamilton 01

CT005 - Chu trình Hamilton 02

CT006 - Chu trình Hamilton 03

DT001 - Ma trận kề - Danh sách cạnh

TRR1001 - 1.1 Đồ thị

TRR1002 - 1.2 Đồ thị

TRR1003 - 1.3 Đồ thị

TRR1004 - 1.4 Đồ thị

TRR1005 - 1.5 Đồ thị

TRR1006 - 1.6 Đồ thị

TRR1007 - 1.7 Đồ thị

TRR1008 - 1.8 Đồ thị

TRR1009 - 1.9 Đồ thị

TRR1010 - 1.10 Đồ thị

TRR1011 - 1.11 Đồ thị

TRR1012 - 1.12 Đồ thị

TRR1013 - 1.13 Đồ thị

TRR1014 - 1.14 Đồ thị

TRR1015 - 1.15 Đồ thị

TRR1016 - 1.16 Đồ thị

TRR1017 - 1.17 Đồ thị

TRR1018 - 1.18 Đồ thị

TRR1019 - 1.19 Đồ thị

TRR1020 - 1.20 Đồ thị

TRR1021 - 1.21 Đồ thị

TRR1022 - 1.22 Đồ thị

TRR2001 - 2.1 Đường đi

TRR2002 - 2.2 Đường đi

TRR2009 - 2.9 Liên thông

TRR2012 - 2.12 Liên thông

TRR2015 - 2.15 Liên thông

TRR2018 - 2.18 Liên thông

TRR2021 - 2.21 Đỉnh trụ

TRR2024 - 2.24 Đỉnh trụ

TRR2027 - 2.27 Cạnh cầu

TRR2030 - 2.30 Cạnh cầu

TRR3001 - 3.1 Chu trình Euler

TRR3004 - 3.4 Chu trình Euler

TRR3007 - 3.7 Chu trình Hamilton

About

Topics

Resources

Stars

Watchers

Forks

Contributors

Languages