สมมติว่าเรามีรายการติดต่อ แต่ละรายการมี username, email, phone ในลำดับใดก็ได้ สองติดต่อถือว่าเป็นคนเดียวกันถ้ามี username หรือ email หรือ phone ตรงกัน หาข้อมูลติดต่อที่เป็นคนเดียวกันจัดกลุ่มรวมกัน
เช่น 4 ติดต่อ ผลลัพธ์: กลุ่ม [0,2,3] และ [1]
ขั้นตอนการแก้ปัญหา (Graph + DFS)
- สร้างกราฟ: โหนด = ติดต่อ, เปลี่ยน = มีข้อมูลตรงกันอย่างน้อย 1 ฟิลด์
- รัน DFS หา Connected Components
- แต่ละ Component คือกลุ่มติดต่อของคนเดียวกัน
ตัวอย่างโค้ด Python
class Contact:
def __init__(self, slot1, slot2, slot3):
self.slot1, self.slot2, self.slot3 = slot1, slot2, slot3
def generate_graph(cnt, n, matrix):
for i in range(n):
for j in range(i+1, n):
if (cnt[i].slot1 == cnt[j].slot1 or cnt[i].slot1 == cnt[j].slot2 or cnt[i].slot1 == cnt[j].slot3 or
cnt[i].slot2 == cnt[j].slot1 or cnt[i].slot2 == cnt[j].slot2 or cnt[i].slot2 == cnt[j].slot3 or
cnt[i].slot3 == cnt[j].slot1 or cnt[i].slot3 == cnt[j].slot2 or cnt[i].slot3 == cnt[j].slot3):
matrix[i][j] = matrix[j][i] = 1
def visit_dfs(i, matrix, visited, sol, n):
visited[i] = True
sol.append(i)
for j in range(n):
if matrix[i][j] and not visited[j]:
visit_dfs(j, matrix, visited, sol, n)
def get_similar_contacts(cnt):
n = len(cnt)
matrix = [[0]*n for _ in range(n)]
visited = [False]*n
generate_graph(cnt, n, matrix)
sol = []
for i in range(n):
if not visited[i]:
visit_dfs(i, matrix, visited, sol, n)
sol.append(-1)
for x in sol:
if x == -1:
print()
else:
print(x, end=" ")
cnt = [
Contact("Amal", "amal@gmail.com", "+915264"),
Contact("Bimal", "bimal321@yahoo.com", "+1234567"),
Contact("Amal123", "+915264", "amal_new@gmail.com"),
Contact("AmalAnother", "+962547", "amal_new@gmail.com")
]
get_similar_contacts(cnt)
อินพุต
4 contacts with overlapping fields
เอาต์พุต
0 2 3 1
