แวดวงเพื่อน

คำอธิบาย

มีนักเรียน N คนในชั้นเรียน บางคนเป็นเพื่อนในขณะที่บางคนไม่ได้ มิตรภาพของพวกเขาเป็นแบบสกรรมกริยา ตัวอย่างเช่น ถ้า A เป็นเพื่อน โดยตรง ของ B และ B เป็นเพื่อนที่ โดยตรง ของ C ดังนั้น A ก็เป็นเพื่อน โดยอ้อม ของ C และเราให้นิยามแวดวงเพื่อนคือกลุ่มนักเรียนที่เป็นเพื่อนทั้งทางตรงและทางอ้อม

ให้เมทริกซ์ N*N M แสดงถึงความสัมพันธ์แบบเพื่อนระหว่างนักเรียนในชั้นเรียน ถ้า M[i][j] = 1 แสดงว่านักเรียนที่ ith และ j เป็นเพื่อนที่ โดยตรง ซึ่งกันและกัน มิเช่นนั้นจะไม่ใช่ และคุณต้องแสดงจำนวนแวดวงเพื่อนทั้งหมดในหมู่นักเรียนทุกคน

ตัวอย่างที่ 1:

Input: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle. 
The 2nd student himself is in a friend circle. So return 2.

ตัวอย่างที่ 2:

Input: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends, 
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.

วิเคราะห์

Friend Cycle เป็นปัญหาคลาสสิกเกี่ยวกับความสัมพันธ์ระหว่างผู้คน โดยทั่วไปเมื่อพูดถึงความสัมพันธ์ เราจะนึกถึงโครงสร้างข้อมูลกราฟทันที โหนดคือผู้คน และขอบคือความสัมพันธ์ เมื่อพูดถึงกราฟ เราควรคิดก่อนว่ากราฟมีทิศทางหรือไม่มีทิศทาง ในปัญหานี้ มิตรภาพคือความสัมพันธ์ระหว่างกัน ดังนั้น กราฟจึงไม่มีทิศทาง และเรายังได้ค่านี้จากเมทริกซ์สมมาตรด้วย

เมื่อเราคิดถึงปัญหานี้ในรูปแบบกราฟ ชีวิตจะง่ายขึ้นมาก เนื่องจากโดยปกติแล้ว เราจะใช้อัลกอริธึมการค้นหากราฟ เช่น DFS และ BFS เพื่อแก้ไขปัญหากราฟ ความแตกต่างที่ใหญ่ที่สุดระหว่างอัลกอริธึมการค้นหาแบบต้นไม้และกราฟคือปัญหาวงกลมหรือการกลับมาเยี่ยมชมอีกครั้ง ซึ่งหมายความว่าเราจำเป็นต้องมีวิธีในการทำเครื่องหมายโหนดว่าเยี่ยมชมแล้วเพื่อหลีกเลี่ยงการกลับมาเยี่ยมชมอีกครั้ง ด้วยวิธีนี้ เราสามารถหาได้ว่าปัญหานี้คือการพยายามหาจำนวนกราฟที่แยกจากกัน

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

เนื่องจากแนวคิด SCC (ส่วนประกอบที่เชื่อมต่ออย่างแข็งแกร่ง) อาจกระโดดเข้ามาในหัวของคุณ ซึ่งก็สมเหตุสมผลดี โดยพื้นฐานแล้ว จุดมุ่งหมายของปัญหาคือการหาจำนวนวงกลมที่อยู่ในหมู่คนทั้งหมด และ SCC จำลองโมเดลวงกลมนั้นอย่างแม่นยำ แน่นอนเราสามารถใช้อัลกอริธึม SCC ที่ซับซ้อนเพื่อแก้ไขปัญหานี้ได้ และหากมิตรภาพเป็นแบบทิศทางเดียว เราก็ต้องใช้มัน อย่างไรก็ตาม ในปัญหานี้ เนื่องจากความสัมพันธ์เป็นแบบเปลี่ยนเส้นทาง จะไม่มีขอบระหว่างสององค์ประกอบ ดังนั้นเราจึงสามารถใช้อัลกอริธึมการค้นหากราฟเพื่อแก้ปัญหาได้

การดำเนินการ

การค้นหากราฟ

เราเริ่มต้นด้วยทุกโหนดที่ยังไม่ได้เยี่ยมชมและขยายกลุ่ม เนื่องจาก Edge ไม่ได้ถูกกำหนดทิศทาง ทุกโหนดที่เชื่อมต่อจะถูกเยี่ยมชมและก่อตัวเป็นกลุ่ม ในระหว่างขั้นตอนนี้ เราสามารถใช้ BSF หรือ DFS เพื่อทำส่วนขยายได้ หลังจากผ่านโหนดทั้งหมดแล้ว เราก็จะได้กลุ่มทั้งหมด

ค้นหายูเนี่ยน

สำหรับ Union-Find วิธีดั้งเดิมคือการแยกขอบออกจากเมทริกซ์ เพื่อที่ว่าสำหรับแต่ละขอบ เราจะสามารถค้นหาพาเรนต์ของโหนดของแต่ละด้าน จากนั้นจึงดำเนินการยูเนี่ยน มีสองวิธีในการดำเนินการ วิธีแรกคือทุกครั้งที่มีการรวมตัวกัน เราจะอัปเดตผู้ปกครองทั้งหมดภายในกลุ่มใดกลุ่มหนึ่ง และในท้ายที่สุด เราจะได้จำนวนของกลุ่มโดยการนับดัชนีที่ไม่ซ้ำกัน อีกวิธีหนึ่งคือการเริ่มต้นหมายเลขกลุ่มด้วยจำนวนโหนดทั้งหมด ทุกครั้งที่มีการรวมกันเกิดขึ้น นั่นหมายความว่ากลุ่มถูกรวมเข้าด้วยกัน ดังนั้นเราจึงลดหมายเลขกลุ่มลง 1 ในระหว่างกระบวนการ เราเพียงต้องอัปเดตหมายเลขกลุ่มที่มากที่สุด ดัชนี.

ซับซ้อน

การค้นหากราฟ

เวลา: เนื่องจากเราแค่ไปตามขอบและเยี่ยมชมทุก ๆ โหนด มันจึงควรเป็น O(n)

Space: เราต้องการสถานที่เก็บข้อมูลการเยี่ยมชมซึ่งก็คือ O(n)

ค้นหายูเนี่ยน

Time: สำหรับแต่ละ Edge เราต้องหาพ่อแม่และทำการรวม ซึ่งก็คือ O(mlogn)

ช่องว่าง: จำเป็นต้องมีช่องว่างเพื่อจัดเก็บข้อมูลหลัก O(n)