สมมติว่าเรามีรายชื่อผู้ติดต่อที่มีชื่อผู้ใช้ อีเมล และหมายเลขโทรศัพท์ในลำดับใด ๆ เราจะต้องค้นหาผู้ติดต่อเดียวกัน (เมื่อบุคคลเดียวกันมีผู้ติดต่อหลายราย) และส่งคืนผู้ติดต่อเดียวกัน ด้วยกัน. เราต้องจำไว้ว่า -
-
ผู้ติดต่อสามารถจัดเก็บชื่อผู้ใช้ อีเมล และช่องโทรศัพท์ได้ตามคำสั่งใดๆ
-
ผู้ติดต่อสองคนจะเหมือนกันหากมีชื่อผู้ใช้หรืออีเมลเดียวกันหรือหมายเลขโทรศัพท์เดียวกัน
ดังนั้น หากอินพุตเป็นเหมือน Contacts =[{"Amal", "[email protected]", "+915264"},{ "Bimal", "[email protected]", " +1234567"},{ "Amal123", "+1234567", "[email protected]"},{ "AmalAnother", "+962547", "[email protected]"}] จากนั้นผลลัพธ์จะเป็น [ 0,2,3], [1] เป็นผู้ติดต่อที่ดัชนี [0,2,3] เหมือนกัน และผู้ติดต่ออื่นที่ดัชนี 1
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน generate_graph() นี่จะใช้เวลา cnt, n, เมทริกซ์
-
สำหรับผมอยู่ในช่วง 0 ถึง n ทำ
-
สำหรับ j ในช่วง 0 ถึง n ทำ
-
เมทริกซ์[i, j] :=0
-
-
-
สำหรับผมอยู่ในช่วง 0 ถึง n ทำ
-
สำหรับ j ในช่วง i + 1 ถึง n ทำ
-
ถ้า cnt[i].slot1 เหมือนกับ cnt[j].slot1 หรือ cnt[i].slot1 เหมือนกับ cnt[j].slot2 orcnt[i].slot1 เหมือนกับ cnt[j].slot3 หรือ cnt[ i].slot2 เหมือนกับ cnt[j].slot1 orcnt[i].slot2 เหมือนกับ cnt[j].slot2 หรือ cnt[i].slot2 เหมือนกับ cnt[j].slot3 orcnt[i].slot3 เหมือนกับ cnt[j].slot1 หรือ cnt[i].slot3 เหมือนกับ cnt[j].slot2 orcnt[i].slot3 เหมือนกับ cnt[j].slot3 ดังนั้น
-
เมทริกซ์[i, j] :=1
-
เมทริกซ์[j, i] :=1
-
ออกจากวง
-
-
-
-
กำหนดฟังก์ชั่น visit_using_dfs() นี่จะใช้เวลา i, matrix, เยี่ยมชม, sol, n
-
เยี่ยมชม[i] :=จริง
-
ใส่ i ต่อท้าย sol
-
สำหรับ j ในช่วง 0 ถึง n ทำ
-
ถ้า matrix[i][j] ไม่ใช่ศูนย์และไม่ได้รับการเข้าชม[j] จะไม่เป็นศูนย์ ดังนั้น
-
visit_using_dfs(j, เมทริกซ์, เยี่ยมชม, โซล, n)
-
-
-
จากวิธีหลัก ให้ทำดังนี้ −
-
n :=ขนาดของ cnt
-
sol :=รายการใหม่
-
matrix :=สร้างเมทริกซ์สี่เหลี่ยมขนาด n x n
-
เยี่ยมชม :=สร้างอาร์เรย์ขนาด n และเติม 0
-
สร้าง_กราฟ(cnt, n, เมทริกซ์)
-
สำหรับผมอยู่ในช่วง 0 ถึง n ทำ
-
ถ้าไม่ได้เยี่ยมชม[i] จะไม่เป็นศูนย์ ดังนั้น
-
visit_using_dfs(i, matrix, เยี่ยมชม, sol, n)
-
ใส่ -1 ที่ส่วนท้ายของโซล
-
-
-
สำหรับฉันในช่วง 0 ถึงขนาดของโซล ทำ
-
ถ้า sol[i] เหมือนกับ -1 แล้ว
-
ไปที่บรรทัดถัดไป
-
-
มิฉะนั้น
-
แสดงโซล[i]
-
-
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
<ก่อนหน้า>คลาสติดต่อ:def __init__(ตัวเอง, slot1, slot2, slot3):self.slot1 =slot1 self.slot2 =slot2 self.slot3 =slot3def generate_graph(cnt, n, matrix):สำหรับฉันในช่วง (n):สำหรับ j ในช่วง (n):matrix[i][j] =0 สำหรับฉันในช่วง (n):สำหรับ j ในช่วง (i + 1, n):if (cnt[i].slot1 ==cnt[j ].slot1 หรือ cnt[i].slot1 ==cnt[j].slot2 หรือ cnt[i].slot1 ==cnt[j].slot3 หรือ cnt[i].slot2 ==cnt[j].slot1 หรือ cnt [i].slot2 ==cnt[j].slot2 หรือ cnt[i].slot2 ==cnt[j].slot3 หรือ cnt[i].slot3 ==cnt[j].slot1 หรือ cnt[i].slot3 ==cnt[j].slot2 หรือ cnt[i].slot3 ==cnt[j].slot3):matrix[i][j] =1 matrix[j][i] =1 breakdef visit_using_dfs(i, เมทริกซ์, เยี่ยมชม, sol, n):เยี่ยมชม[i] =True sol.append(i) สำหรับ j ในช่วง (n):if (matrix[i][j] and not visit[j]):visit_using_dfs(j, matrix, เยี่ยมชม, โซล, n)def get_similar_contacts(cnt):n =len(cnt) sol =[] matrix =[[ไม่มี] * n สำหรับฉันในช่วง (n)] เยี่ยมชม =[0] * n สร้างกราฟ (c nt, n, matrix) สำหรับฉันในช่วง (n):ถ้า (ไม่ได้เยี่ยมชม [i]):visit_using_dfs (i, matrix, เยี่ยมชม, sol, n) sol.append(-1) สำหรับฉันในช่วง (len (sol )):if (sol[i] ==-1):print() else:print(sol[i], end =" ")cnt =[contact("Amal", "[email protected]", " +915264"), ผู้ติดต่อ("Bimal", "[email protected]", "+1234567"), ผู้ติดต่อ("Amal123", "+915264", "[email protected]"), ผู้ติดต่อ("AmalAnother" , "+962547", "[email protected]")]get_similar_contacts(cnt)อินพุต
cnt =[ติดต่อ("Amal", "[email protected]", "+915264"),ติดต่อ("Bimal", "[email protected]", "+1234567"),ติดต่อ("Amal123 ", "+915264", "[email protected]"),ติดต่อ("AmalAnother", "+962547", "[email protected]")] ผลลัพธ์
0 2 31
