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