สมมติว่าเราได้รับจำนวนโหนดและขอบ N และ M ตามลำดับ จากนั้นเราจะทราบว่าโหนดใดเชื่อมต่ออยู่ เราจะหาจำนวน Edge พิเศษขั้นต่ำที่จำเป็นในการเชื่อมต่อให้เสร็จสมบูรณ์ได้อย่างไร เพื่อให้คุณสามารถเยี่ยมชมทุกโหนดได้อย่างไร โดยการค้นหาคำตอบ คุณจะสามารถข้ามไปยังทุกโหนดได้ ไม่ว่าจะไปโดยตรงหรือผ่านโหนดอื่นเพื่อไปยังเป้าหมาย
ตัวอย่างอินพุต:
4 2 (โหนดและขอบ)
0 1 (เชื่อมต่อโหนด 0 และโหนด 1)
2 3 (เชื่อมต่อโหนด 2 และโหนด 3)
ซึ่งควรให้คำตอบแก่เรา 1 เราต้องการขอบพิเศษหนึ่งอันเพื่อทำการเชื่อมต่อให้เสร็จสมบูรณ์
สิ่งที่คุณต้องการคือ:
1) ค้นหาส่วนประกอบที่เชื่อมต่อ สามารถทำได้โดย dfs หรือ bfs ในตัวอย่างของคุณ ส่วนประกอบเหล่านี้คือ 0, 1 และ 2, 3 ตามลำดับ
2) จากนั้นคุณจะต้องวนซ้ำส่วนประกอบทั้งหมดและเชื่อมต่อจุดยอดสองจุดใดๆ สำหรับทุก ๆ สององค์ประกอบที่ตามมา ด้วยวิธีนี้ คุณจะเชื่อมต่อส่วนประกอบที่หนึ่งและที่สอง จากนั้นจึงเชื่อมต่อส่วนประกอบที่สองและสาม และอื่นๆ... ในตัวอย่างของคุณ คุณสามารถเชื่อมต่อจุดยอดใดๆ 0, 1 กับจุดยอดใดก็ได้ 2, 3 ตัวอย่างเช่น คุณสามารถเชื่อมต่อจุดยอด 0 และ 2 ได้
สังเกตได้ง่ายว่าถ้าจำนวนส่วนประกอบทั้งหมดเท่ากับ C คำตอบจะเป็น C - 1 ขอบเพิ่มเติม
จำนวนการเชื่อมต่อขั้นต่ำที่จำเป็นสำหรับการเชื่อมต่อกราฟของคุณคือ N-1 แต่สิ่งนี้จะคงอยู่หากไม่มีโหนดที่มีการเชื่อมต่อ 0
ลองนึกภาพเส้นทางที่คล้ายกับการออกแบบรายการที่เชื่อมต่อกัน ทุกโหนดมีดีกรีเป็น 2 พอดี ยกเว้นจากปลายทั้งสองด้าน ด้วยวิธีนี้ (สมมติว่าการเชื่อมต่อของคุณไม่ได้ถูกกำหนดทิศทาง) โดยเริ่มจากโหนดใดๆ คุณสามารถเข้าถึงเป้าหมายของคุณได้โดยเพียงแค่ไปที่โหนดถัดไปที่ยังไม่ได้เยี่ยมชม
หาก M>N-1 คุณสามารถค้นหาโหนดที่มีการเชื่อมต่อเกินความจำเป็นและดำเนินการต่อจากที่นั่น
ลองนับการเชื่อมต่อเพิ่มเติมแล้วเปรียบเทียบกับจำนวนขั้นต่ำที่ต้องการ (N-1)
