मान लीजिए हमारे पास कॉन्टैक्ट्स की एक सूची है जिसमें यूजरनेम, ईमेल और फोन नंबर किसी भी क्रम में हैं, हमें समान कॉन्टैक्ट्स ढूंढने हैं (जब एक ही व्यक्ति के कई अलग-अलग कॉन्टैक्ट्स हों) और समान कॉन्टैक्ट्स को एक साथ लौटाना है। हमें ध्यान रखना होगा कि:
एक कॉन्टैक्ट यूजरनेम, ईमेल और फोन फील्ड्स को किसी भी क्रम में स्टोर कर सकता है।
दो कॉन्टैक्ट्स समान हैं यदि उनका यूजरनेम या ईमेल या फोन नंबर समान है।
तो, यदि इनपुट 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] होगा क्योंकि इंडेक्स [0,2,3] पर कॉन्टैक्ट्स समान हैं, और इंडेक्स 1 पर एक और कॉन्टैक्ट है।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
generate_graph() फंक्शन परिभाषित करें। यह cnt, n, matrix लेगा।
i को 0 से n तक के लिए, करें:
j को 0 से n तक के लिए, करें:
matrix[i, j] := 0
i को 0 से n तक के लिए, करें:
j को i+1 से n तक के लिए, करें:
यदि 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
लूप से बाहर निकलें
visit_using_dfs() फंक्शन परिभाषित करें। यह i, matrix, visited, sol, n लेगा।
visited[i] := True
sol के अंत में i डालें
j को 0 से n तक के लिए, करें:
यदि matrix[i][j] शून्येतर है और not visited[j] शून्येतर है, तो:
visit_using_dfs(j, matrix, visited, sol, n)
मुख्य विधि से, निम्नलिखित करें:
n := cnt का आकार
sol := एक नई सूची
matrix := आकार n x n का एक वर्ग मैट्रिक्स बनाएं
visited := आकार n का एक ऐरे बनाएं, और 0 से भरें
generate_graph(cnt, n, matrix)
i को 0 से n तक के लिए, करें:
यदि not visited[i] शून्येतर है, तो:
visit_using_dfs(i, matrix, visited, sol, n)
sol के अंत में -1 डालें
i को 0 से sol के आकार तक के लिए, करें:
यदि sol[i], -1 के समान है, तो:
अगली पंक्ति पर जाएं
अन्यथा,
sol[i] प्रदर्शित करें
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
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 i in range(n)] visited = [0] * 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 i in range(len(sol)): if (sol[i] == -1): print() else: print(sol[i], 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)इनपुट
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")]आउटपुट
0 2 3 1
