पायथन में एक पेड़ में ठीक k की दूरी वाले अलग-अलग जोड़े के जोड़े की संख्या ज्ञात करें

मान लीजिए कि हमारे पास एक पूर्णांक k है और n नोड्स वाला एक ट्री भी है, तो हमें उन अलग-अलग युग्मों की संख्या गिननी होगी जिनकी सटीक k दूरी है।

तो, अगर इनपुट k =2 जैसा है

तो आउटपुट 4

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एन:=5005

• ग्राफ़ :=आकार N की आसन्नता सूची

• vertex_count :=505 x 5005 आकार का 2d मैट्रिक्स

• रेस :=0

• एक फ़ंक्शन को परिभाषित करें insert_edge() । इसमें x, y लगेगा

  • ग्राफ़ के अंत में y डालें[x]

  • ग्राफ़ के अंत में x डालें[y]

• फ़ंक्शन को परिभाषित करें dfs() । यह वी, माता-पिता को लेगा

• vertex_count[v, 0] :=1

• ग्राफ़ में प्रत्येक i के लिए[v], करें

  • अगर मैं माता-पिता के समान नहीं हूं, तो

    • dfs(i, v)

    • j के लिए 1 से k + 1 की श्रेणी में, करें

      • रेस:=रेस + वर्टेक्स_काउंट [आई, जे -1] * वर्टेक्स_काउंट [वी, के - जे]

    • j के लिए 1 से k + 1 की श्रेणी में, करें

      • vertex_count[v, j] :=vertex_count[v, j] + vertex_count[i, j-1]

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

N = 5005
graph = [[] for i in range(N)]
vertex_count = [[0 for i in range(505)] for i in range(N)]
res = 0
def insert_edge(x, y):
   graph[x].append(y)
   graph[y].append(x)
def dfs(v, parent):
   global res
   vertex_count[v][0] = 1
   for i in graph[v]:
      if (i != parent):
         dfs(i, v)
         for j in range(1, k + 1):
            res += vertex_count[i][j - 1] * vertex_count[v][k - j]
         for j in range(1, k + 1):
            vertex_count[v][j] += vertex_count[i][j - 1]
k = 2
insert_edge(1, 2)
insert_edge(2, 3)
insert_edge(3, 4)
insert_edge(2, 5)
dfs(1, 0)
print(res)

इनपुट

k = 2
insert_edge(1, 2)
insert_edge(2, 3)
insert_edge(3, 4)
insert_edge(2, 5)

आउटपुट

4