ในบทความนี้ เราจะอธิบายข้อมูลสำคัญเกี่ยวกับการแก้ไขจำนวนโหนด sinks ในกราฟ เรามี Directed Acyclic Graph ที่มีโหนด N (1 ถึง N) และขอบ M ในปัญหานี้ เป้าหมายคือการค้นหาว่ามีโหนดซิงก์จำนวนเท่าใดในกราฟที่กำหนด โหนดซิงก์คือโหนดที่ไม่สร้างขอบขาออกใดๆ นี่เป็นตัวอย่างง่ายๆ −
Input : n = 4, m = 2
Edges[] = {{2, 3}, {4, 3}}
Output : 2 แนวทางง่ายๆ ในการค้นหาวิธีแก้ปัญหา
ในแนวทางนี้ เราจะผ่านขอบของกราฟ ผลักองค์ประกอบที่แตกต่างกันในชุดที่จะไปถึงขอบ จากนั้นลบขนาดของชุดด้วยจำนวนโหนดทั้งหมดที่มีอยู่
ตัวอย่าง
#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;
} ผลลัพธ์
2
คำอธิบายของโค้ดด้านบน
ในรหัสนี้ เราจะข้ามผ่านขอบเวกเตอร์และแทรกองค์ประกอบแรกของทั้งคู่ลงในชุด มันเก็บเฉพาะองค์ประกอบที่แตกต่างกัน ดังนั้นตอนนี้เราจะลบขนาดเฉพาะของชุดออกจากจำนวนโหนดทั้งหมด โปรแกรมที่แสดงข้างต้นมีความซับซ้อนของเวลาเป็น O(N) โดยที่ N หมายถึงจำนวนขอบที่มีอยู่ในกราฟ
บทสรุป
ในบทความนี้ เราได้แก้ไขปัญหาในการค้นหาจำนวนโหนดซิงก์ที่มีอยู่ในความซับซ้อนของเวลาของกราฟ O(N) โดยใช้ชุดข้อมูล นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ หวังว่าบทความนี้จะเป็นประโยชน์
