Cho đồ thị có hướng không chu trình (DAG) với N nút (1 đến N) và M cạnh. Nút hứng (sink node) là nút không có cạnh đi ra. Nhiệm vụ: đếm số nút hứng.
Ví dụ
Input: n = 4, m = 2, Edges = {{2, 3}, {4, 3}} Output: 2
Nút 1 và 2 không có cạnh đi ra? Kiểm tra: cạnh từ 2→3, 4→3. Nút 1, 2, 4 có cạnh đi ra? 2 có, 4 có. Nút 1 và 3 không có cạnh đi ra → 2 nút hứng.
Phương pháp
Duyệt qua các cạnh, thu thập tập hợp các nút có cạnh đi ra (phần tử đầu của cặp). Số nút hứng = N - kích thước tập hợp.
Mã nguồn C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 4;
int m = 2;
vector<pair<int, int>> edges = {{2, 3}, {4, 3}};
set<int> s;
for (int i = 0; i < m; i++) {
s.insert(edges[i].first);
}
cout << n - s.size();
return 0;
}
Kết quả
2
Giải thích
Set s lưu các nút xuất phát của cạnh (loại trùng lặp). Kích thước set = số nút không phải nút hứng. Trừ từ tổng số nút n ra số nút hứng. Độ phức tạp O(M log M) do set, có thể O(M) dùng vector
Kết luận
Bài viết giải quyết bài toán đếm nút hứng trong đồ thị có hướng bằng set. Độ phức tạp O(M log M). Mã nguồn C++ đơn giản, có thể triển khai bằng các ngôn ngữ khác.