โปรแกรม C++ หาจุดยอดในกราฟ

สมมติว่าเราได้กราฟที่มีจุดยอด n จุด จุดยอดมีหมายเลข 1 ถึง n และเชื่อมต่อด้วยขอบที่ระบุใน 'ขอบ' ของอาร์เรย์ จุดยอดแต่ละอันมีค่า 'x' ภายในตัวเลขตั้งแต่ 1 ถึง n ซึ่งกำหนดไว้ใน 'ค่า' ของอาร์เรย์ ตอนนี้ เราต้องหาจุดยอดสุดยอดจากกราฟ จุดยอด i เรียกว่า 'ยอดสุดยอด' เมื่อใดก็ตามที่เส้นทางที่สั้นที่สุดจากจุดยอด 1 ถึง i ไม่มีจุดยอดที่มีค่า 'x' เหมือนกันกับจุดยอดที่ i เราพิมพ์จุดยอดทั้งหมดที่เป็นไปตามเกณฑ์นี้

ดังนั้น หากอินพุตเป็น n =5 ค่า ={1, 2, 2, 1, 3}, ขอบ ={{1, 2}, {2, 3}, {2, 3}, {2, 4 }, {4, 5}} แล้วผลลัพธ์จะเป็น 1 3 4 5.

ทุกจุดยอดยกเว้นจุดยอด 2 เป็นไปตามเกณฑ์ ดังนั้น ไม่รวมจุดยอด 2

ขั้นตอน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดอาร์เรย์ vertexVal, frq และ chk ของขนาด:100005.กำหนดอาร์เรย์ vcti ที่มีขนาด 200005.กำหนดฟังก์ชัน dfs() ซึ่งจะใช้ j, k ถ้า frq[vertexVal[j]] เหมือนกับ 0 จากนั้น:chk[j] :=1 (เพิ่ม frq[vertexVal[j]] โดย 1) สำหรับแต่ละค่า a ใน vcti[j] ทำ:ถ้า a ไม่เท่ากับ k ดังนั้น:dfs(a, j) (ลด frq[vertexVal[j]] โดย 1) สำหรับการเริ่มต้น i :=0 เมื่อฉัน  
ตัวอย่าง
 

 ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
 
#include ใช้เนมสเปซ std;int n;int vertexVal[100005], frq[100005], chk[100005];vector vcti[200005];void dfs(int j, int k){ ถ้า (frq[vertexVal[j]] ==0) chk[j] =1; frq[vertexVal[j]]++; สำหรับ (อัตโนมัติ a :vcti[j]) { if (a !=k) dfs(a, j); } frq[vertexVal[j]]--;} โมฆะแก้ปัญหา (int ค่า[], vector> ขอบ){ สำหรับ (int i =0; i > ขอบ ={{1, 2}, {2, 3}, {2, 3}, {2, 4}, {4, 5}}; แก้(ค่า, ขอบ); คืนค่า 0;}
 
อินพุต
 <ก่อนหน้า>5, {1, 2, 2, 1, 3}, {{1, 2}, {2, 3}, {2, 3}, {2, 4}, {4, 5}} 
ผลลัพธ์
 
1345