Trong bài viết này, chúng tôi sẽ mô tả thông tin quan trọng về việc giải quyết số lượng nút chìm trong đồ thị. Chúng ta có Đồ thị vòng có hướng với N nút (1 đến N) và M cạnh trong bài toán này. Mục đích là tìm xem có bao nhiêu nút chìm trong đồ thị đã cho. Nút chìm là nút không tạo ra bất kỳ cạnh đi nào. Đây là một ví dụ đơn giản -
Input : n = 4, m = 2
Edges[] = {{2, 3}, {4, 3}}
Output : 2 Phương pháp tiếp cận đơn giản để tìm giải pháp
Trong cách tiếp cận này, chúng ta sẽ đi qua các cạnh của biểu đồ, đẩy các phần tử khác biệt trong tập hợp mà các cạnh sẽ đi từ đó trừ kích thước của tập hợp với tổng số nút hiện có.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main(){
int n = 4; // number of nodes.
int m = 2; // number of edges.
vector<pair<int, int>> edges = {{2, 3}, {4, 3}}; // the edges going from first to second.
set<int> s;
for(int i = 0; i < m; i++){
s.insert(edges[i].first); // will keep value of
// distinct node from which edges are going out.
}
cout << n - s.size(); // answer is the total number of nodes - number of non sink nodes.
return 0;
} Đầu ra
2
Giải thích về Quy tắc trên
Trong đoạn mã này, chúng ta sẽ duyệt qua các cạnh vectơ và chèn phần tử đầu tiên của cặp vào một tập hợp. Nó chỉ giữ các phần tử riêng biệt, vì vậy bây giờ chúng ta sẽ lấy tổng số nút trừ đi kích thước cụ thể của tập hợp. Chương trình được hiển thị ở trên có độ phức tạp về thời gian là O (N) trong đó N là số cạnh có trong biểu đồ.
Kết luận
Trong bài viết này, chúng tôi đã giải quyết vấn đề tìm Số nút chìm có trong đồ thị độ phức tạp thời gian O (N) bằng cách sử dụng sự trợ giúp của một tập hợp. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Hy vọng bạn thấy bài viết này hữu ích.