Tìm liên hệ trùng lặp trong danh sách liên hệ trong Python

Cho danh sách liên hệ, mỗi liên hệ có username, email, phone (thứ tự bất kỳ). Hai liên hệ là cùng một người nếu cùng username HOẶC email HOẶC phone. Gom nhóm các liên hệ trùng nhau.

Ví dụ: 4 liên hệ → nhóm [0,2,3] và [1].

Giải thuật (Đồ thị + DFS)

• Xây đồ thị: đỉnh = liên hệ, cạnh giữa 2 liên hệ nếu có ít nhất 1 trường trùng.
• DFS/BFS tìm các thành phần liên thông.
• Mỗi thành phần liên thông là một nhóm người cùng danh tính.

Ví dụ

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(n):
            matrix[i][j] = 0
    for i in range(n):
        for j in range(i+1, n):
            if (cnt[i].slot1 in (cnt[j].slot1, cnt[j].slot2, cnt[j].slot3) or
                cnt[i].slot2 in (cnt[j].slot1, cnt[j].slot2, cnt[j].slot3) or
                cnt[i].slot3 in (cnt[j].slot1, cnt[j].slot2, 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)
    sol = []
    matrix = [[0]*n for _ in range(n)]
    visited = [False]*n
    generate_graph(cnt, n, matrix)
    for i in range(n):
        if not visited[i]:
            visit_dfs(i, matrix, visited, sol, n)
            sol.append(-1)
    for v in sol:
        if v == -1:
            print()
        else:
            print(v, 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)

Đầu vào

4 contacts with overlapping info

Đầu ra

0 2 3 1