Đề: UVa 00315 Network Abridge: Bài toán tìm Articulation Point điển hình Solution: Using Articulation Point dfs to find, nhớ là lúc đọc input thì + cin >> integer ko đọc '\n' => dùng thêm cin.ignore(); + stringstream ss; ss.clear() để xóa đệm, eof,... + getline (cin,line) thường đi đôi với stringstream. Code:
Đề: 11080 Place the Guards Abridge: Có v (vertices) junction (giao lộ) và e (edges) streets (con đường). Một Guard (bảo vệ) đặt tại mỗi vertex (giao lộ) sẽ bảo vệ các junctions và street cận kề. Nếu 2 guards cùng bảo vệ 1 con đường sẽ gây ra đánh nhau. Tìm số bảo vệ ít nhất để bảo vệ tất cả con đường và giao lộ sao cho không xảy ra xung đột. Solution: Bipartite Graph Check + numCC Vì Graph có nhiều connected component nên: Các CC độc lập với nhau. Với mỗi CC ta lần lượt color vertex đầu = 0 (no guard) hoặc 1 (guards here), nếu cả 2 trường hợp đều return -1 (mâu thuận or ko cover) thì printf("-1"), còn nếu có cái nào được thì lấy cái đó, 2 cái đều được thì lấy min. * Lưu ý: Khi CC chỉ có 1 vertex thì 1 TH duy nhất là phải color nó = 1 (guard here) Code:
Đề: 11060 Beverages Abridge: In ra duy nhất 1 topological order với khác biệt: In the case there is no relation between 2 bevarages, Dilbert should start drinking the one that appers first in the input. Khi không có quan hệ giữa 2 loại thức uống thì uống theo thứ tự xuất hiện trong input. Solution: Dùng Kahn 's Algorithms + duyệt theo thứ tự input Tham khảo http://www.algorithmist.com/index.php/UVa_11060 Code:
Đề: 10305 Ordering Tasks Abridge: Xuất ra 1 trật tự topology đúng, có nhiều topological Ordering nhưng chỉ cần xuất ra 1 order là được Solution: Using dfs + lưu lại thứ tự finish các công việc (nodes) , sau đó reverse lại thứ tự đó ta được 1 topological ordering. Chứng minh: DFS, Topology Sort (38:23) Code:
Đề 00872 Ordering Abridge : In ra tất cả các topological ordering. Solution: Sử dụng backtracking để sinh hoán vị, nhớ là phải check điều kiện xem tại vị trí ans[i] đó có thể đặt nodes đó hay không. Một nodes có thể đặt là khi những nodes sau nó (edges[nodes][j]) phải chưa được đặt, ta viết hàm valid() để check. Code: