การเชื่อมต่อที่สำคัญในเครือข่ายใน C++

สมมติว่ามีเซิร์ฟเวอร์ n เซิร์ฟเวอร์ และสิ่งเหล่านี้มีหมายเลขตั้งแต่ 0 ถึง n-1 ที่เชื่อมต่อโดยการเชื่อมต่อระหว่างเซิร์ฟเวอร์กับเซิร์ฟเวอร์แบบไม่มีทิศทางซึ่งสร้างเครือข่ายโดยที่การเชื่อมต่อ[i] =[a,b] แสดงถึงการเชื่อมต่อระหว่างเซิร์ฟเวอร์ a และ b เซิร์ฟเวอร์ทั้งหมดเชื่อมต่อโดยตรงหรือผ่านเซิร์ฟเวอร์อื่น ตอนนี้ การเชื่อมต่อที่สำคัญคือการเชื่อมต่อที่หากลบออก จะทำให้เซิร์ฟเวอร์บางเครื่องไม่สามารถเข้าถึงเซิร์ฟเวอร์อื่นได้ เราต้องหาการเชื่อมต่อที่สำคัญทั้งหมด

ดังนั้น หากอินพุตเป็น n =4 และการเชื่อมต่อ =[[0,1],[1,2],[2,0],[1,3]],

จากนั้นผลลัพธ์จะเป็น [[1,3]]

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

• กำหนดหนึ่งชุด

• กำหนดดิสก์อาร์เรย์

• กำหนดอาร์เรย์ต่ำ

• กำหนดอาร์เรย์ 2D ret หนึ่งรายการ

• กำหนดฟังก์ชัน dfs() ซึ่งจะใช้โหนด พาร์ หนึ่งกราฟอาร์เรย์ 2 มิติ

• ถ้าโหนดอยู่ในการเยี่ยมชมแล้ว −

  • กลับ

• แทรกโหนดเข้าเยี่ยมชม

• ดิสก์[โหนด] :=เวลา

• ต่ำ[โหนด] :=เวลา

• (เพิ่มเวลาขึ้นอีก 1)

• สำหรับทุกองค์ประกอบ x ในกราฟ[โหนด]

  • ถ้า x เท่ากับพาร์ แล้ว −

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • ถ้า x ไม่อยู่ในการเยี่ยมชม −

    • dfs(x, โหนด, กราฟ)

    • low[node] :=ต่ำสุดของ low[node] และ low[x]

    • ถ้าดิสก์[โหนด] <ต่ำ[x] แล้ว −

      • แทรก { node, x } ที่ส่วนท้ายของ ret

  • มิฉะนั้น

    • low[node] :=ต่ำสุดของ low[node] และ disc[x]

• จากวิธีหลัก ให้ทำดังนี้ −

  • กำหนดขนาดของแผ่นดิสก์เป็น n + 1

  • กำหนดขนาดต่ำเป็น n + 1

  • เวลา :=0

  • กำหนดอาร์เรย์ของรายการของกราฟขนาด n + 1

  • สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาด v อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

    • u :=v[i, 0]

    • w :=v[i, 1]

    • แทรก w ที่ส่วนท้ายของกราฟ[u]

    • ใส่ u ที่ท้ายกราฟ[w]

  • dfs(0, -1, กราฟ)

  • รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include ใช้เนมสเปซ std;void print_vector(vector> v){ cout <<"["; for(int i =0; i เยี่ยมชม; เวกเตอร์ ดิสก์; เวกเตอร์ ต่ำ; ทันเวลา; vector> ย้อนกลับ; โมฆะ dfs (โหนด int, int par, vector  กราฟ []) { if (visited.count (node)) ส่งคืน; visit.insert(โหนด); ดิสก์[โหนด] =ต่ำ[โหนด] =เวลา; เวลา++; สำหรับ (int x:กราฟ [โหนด]) { ถ้า (x ==พาร์) ดำเนินการต่อ; if (!visited.count(x)) { dfs(x, node, graph); ต่ำ[โหนด] =นาที(ต่ำ[โหนด], ต่ำ[x]); ถ้า (ดิสก์ [โหนด] <ต่ำ [x]) { ret.push_back ({ โหนด x }); } } อื่น ๆ { ต่ำ [โหนด] =นาที (ต่ำ [โหนด], ดิสก์ [x]); } } } vector> criticalConnections(int n, vector>&v) { disc.resize(n + 1); low.resize(n + 1); เวลา =0; เวกเตอร์ กราฟ[n + 1]; สำหรับ (int i =0; i > v ={{0,1},{1,2},{2,0},{1,3}}; print_vector(ob.criticalConnections(4,v));}

อินพุต

ผลลัพธ์

[[1, 3, ],]