मान लीजिए कि हमारे पास किसी भी क्रम में उपयोगकर्ता नाम, ईमेल और फोन नंबर रखने वाले संपर्कों की एक सूची है, हमें वही संपर्क ढूंढना होगा (जब एक ही व्यक्ति के कई अलग-अलग संपर्क हों) और वही संपर्क वापस करें साथ में। हमें यह ध्यान रखना होगा कि -
-
एक संपर्क किसी भी क्रम के अनुसार उपयोगकर्ता नाम, ईमेल और फोन फ़ील्ड को स्टोर कर सकता है।
-
दो संपर्क समान हैं यदि उनके पास एक ही उपयोगकर्ता नाम या एक ही ईमेल या एक ही फोन नंबर है।
तो, यदि इनपुट जैसे संपर्क =[{"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, मैट्रिक्स लेगा
-
मेरे लिए 0 से n की सीमा में, करें
-
j के लिए 0 से n की सीमा में, करें
-
मैट्रिक्स [i, j] :=0
-
-
-
मेरे लिए 0 से n की सीमा में, करें
-
i + 1 से n की श्रेणी में j के लिए, करें
-
अगर 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] के समान है। स्लॉट2 cnt[j].slot3 orcnt[i].slot3 के समान है। cnt[j].slot1 या cnt[i].slot3 के समान है, cnt[j].slot2 orcnt[i].slot3 के समान है, cnt[j].slot3 के समान है, फिर
-
मैट्रिक्स [i, j] :=1
-
मैट्रिक्स [जे, आई] :=1
-
लूप से बाहर आएं
-
-
-
-
एक फ़ंक्शन को परिभाषित करें visit_using_dfs() । यह ले जाएगा i, मैट्रिक्स, विज़िट किया गया, सोल, n
-
दौरा किया [i] :=सच
-
सोल के अंत में i डालें
-
j के लिए 0 से n की सीमा में, करें
-
यदि मैट्रिक्स [i] [j] गैर-शून्य है और विज़िट नहीं किया गया है [j] गैर-शून्य है, तो
-
visit_using_dfs(j, मैट्रिक्स, विज़िट किया गया, सोल, n)
-
-
-
मुख्य विधि से, निम्न कार्य करें -
-
n :=cnt का आकार
-
सोल:=एक नई सूची
-
मैट्रिक्स:=आकार n x n का एक वर्ग मैट्रिक्स बनाएं
-
विज़िट किया गया :=आकार n की एक सरणी बनाएं, और 0 से भरें
-
Generate_graph(cnt, n, मैट्रिक्स)
-
मेरे लिए 0 से n की सीमा में, करें
-
यदि विज़िट नहीं किया गया है [i] गैर-शून्य है, तो
-
visit_using_dfs(i, मैट्रिक्स, विज़िट किया गया, सोल, n)
-
सोल के अंत में -1 डालें
-
-
-
मैं के लिए 0 से सोल के आकार की सीमा में, ऐसा करें
-
अगर सोल [i] -1 के समान है, तो
-
अगली पंक्ति पर जाएँ
-
-
अन्यथा,
-
प्रदर्शन सोल[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
