จัดลำดับเส้นทางใหม่เพื่อสร้างเส้นทางทั้งหมดนำไปสู่ศูนย์เมืองใน C++

สมมติว่ามีเมืองที่แตกต่างกัน n เมืองที่มีหมายเลขตั้งแต่ 0 ถึง n-1 และยังมีถนน n-1 ซึ่งมีเพียงวิธีเดียวเท่านั้นที่จะเดินทางระหว่างสองเมืองที่ต่างกัน สมมุติว่ากระทรวงคมนาคมตัดสินใจปรับทิศทางถนนในทิศทางเดียวเพราะแคบเกินไป

ในที่นี้ ถนนต่างๆ จะถูกแสดงโดยการเชื่อมต่อโดยที่จุดเชื่อมต่อ[i] =[a, b] หมายถึงถนนจากเมือง a ไปยัง b

หากมีงานใหญ่ในเมืองหลวง (เมืองเลข 0) และหลายคนอยากไปเที่ยวเมืองนี้ เราต้องดำเนินการปรับทิศทางใหม่บนถนนบางสายเพื่อให้แต่ละเมืองสามารถเยี่ยมชมเมือง 0 ได้ เราต้องหาจำนวนขอบขั้นต่ำที่เปลี่ยนไป

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

จากนั้นเอาต์พุตจะเป็น 3 เนื่องจากเราต้องเปลี่ยนทิศทางของขอบที่แสดงเป็นสีแดงเพื่อให้แต่ละโหนดสามารถไปถึงเมืองหลวงได้

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

• กำหนดสองอาร์เรย์ของรายการ graph1, graph2 ขนาด N =5*10^4 + 5

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• กำหนดหนึ่งแผนที่ใน

• สำหรับแต่ละองค์ประกอบใน e ทำ

  • ใส่มัน[1] ที่ส่วนท้ายของกราฟ1[it[0]]

  • ใส่มัน[0] ที่ส่วนท้ายของกราฟ2[it[1]]

• กำหนดอาร์เรย์ dist ขนาด n และเติมด้วย N + 10

• ret :=0, ใน[0] :=0, dist[0] :=0

• กำหนดหนึ่งคิว q

• ใส่ 0 ลงใน q

• กำหนดการเยี่ยมชมหนึ่งชุด

• ใส่ 0 เข้าไป

• ในขณะที่ (ไม่ใช่ q ว่างเปล่า) ทำ -

  • โหนด :=องค์ประกอบแรกของ q

  • ลบองค์ประกอบออกจาก q

  • ret :=ret + dist[โหนด]

  • สำหรับแต่ละองค์ประกอบใน graph2[node] ทำ

    • ถ้าไม่ได้เยี่ยมชมและ dist[it]> 0 แล้ว −

      • dist[it] :=0

      • แทรกลงใน q

      • ใส่เข้าไป

  • สำหรับแต่ละองค์ประกอบใน graph1[node] ทำ

    • ถ้าไม่ได้เยี่ยมชมและ dist[it]> 1 แล้ว −

      • dist[it] :=1

      • แทรกลงใน q

      • ใส่เข้าไป

• รีเทิร์น

ตัวอย่าง

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

#include ใช้เนมสเปซ std;const int N =5e4 + 5;คลาสโซลูชัน {สาธารณะ:vector graph1[N]; เวกเตอร์ กราฟ2[N]; int minReorder(int n, vector>&e){ map ใน; สำหรับ (อัตโนมัติ&มัน:จ) { graph1[it[0]].push_back(it[1]); graph2[it[1]].push_back(it[0]); } vector dist(n, N + 10); int ret =0; ใน[0] =0; dist[0] =0; คิว q; q.push(0); set เยี่ยมชม; เยี่ยมชม.insert(0); ในขณะที่ (!q.empty()) { โหนด int =q.front(); q.ป๊อป(); ret +=dist[โหนด]; สำหรับ (อัตโนมัติ&มัน:graph2[โหนด]) { if (!visited.count(it) &&dist[it]> 0) { dist[it] =0; q.push(มัน); visit.insert(มัน); } } for (auto&it:graph1[node]) { if (!visited.count(it) &&dist[it]> 1) { dist[it] =1; q.push(มัน); visit.insert(มัน); } } } ส่งคืน ret; }};main(){ โซลูชัน ob; เวกเตอร์<เวกเตอร์> v ={{0,1},{1,3},{2,3},{4,0},{4,5}}; cout <<(ob.minReorder(6,v));}

อินพุต

ผลลัพธ์

3