পাইথনে কন্ট্যাক্ট লিস্টে একই ব্যক্তির একাধিক কন্ট্যাক্ট গোষ্ঠীবদ্ধ করা

একটি কন্ট্যাক্ট লিস্ট দেওয়া আছে যেখানে প্রতিটি কন্ট্যাক্টে ইউজারনেম, ইমেইল এবং ফোন নম্বর যেকোনো ক্রমে থাকতে পারে। একই ব্যক্তির একাধিক কন্ট্যাক্ট থাকলে সেগুলো একসাথে গোষ্ঠীবদ্ধ (group) করতে হবে। দুটি কন্ট্যাক্ট একই ব্যক্তির যদি ইউজারনেম বা ইমেইল বা ফোন নম্বর মিলে।

উদাহরণ

ইনপুট: Contacts = [{"Amal", "amal@gmail.com", "+915264"}, {"Bimal", "bimal321@yahoo.com", "+1234567"}, {"Amal123", "+1234567", "amal_new@gmail.com"}, {"AmalAnother", "+962547", "amal_new@gmail.com"}]

আউটপুট: [0,2,3], [1] (ইনডেক্স ০,২,৩ একই ব্যক্তির, ১ আলাদা)

সমাধানের পদ্ধতি

গ্রাফ (Graph) মডেলিং: প্রতিটি কন্ট্যাক্ট একটি নোড।
দুটি কন্ট্যাক্টের মধ্যে যেকোনো ফিল্ড (username/email/phone) মিললে এজ (edge) তৈরি।
DFS (Depth First Search) ব্যবহার করে কানেক্টেড কম্পোনেন্ট (connected component) খুঁজে বের করা।
প্রতিটি কম্পোনেন্ট হলো একই ব্যক্তির কন্ট্যাক্ট গোষ্ঠী।

পাইথন কোড


class Contact:
    def __init__(self, slot1, slot2, slot3):
        self.slot1 = slot1
        self.slot2 = slot2
        self.slot3 = 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 == 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] = 1
                matrix[j][i] = 1
                break

def visit_using_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_using_dfs(j, matrix, visited, sol, n)

def get_similar_contacts(cnt):
    n = len(cnt)
    sol = []
    matrix = [[None] * n for _ in range(n)]
    visited = [False] * n
    generate_graph(cnt, n, matrix)
    for i in range(n):
        if not visited[i]:
            visit_using_dfs(i, matrix, visited, sol, n)
            sol.append(-1)
    for val in sol:
        if val == -1:
            print()
        else:
            print(val, 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)

ইনপুট

Contact অবজেক্টের লিস্ট

আউটপুট

0 2 3
1