पायथन में ट्री में ठीक k दूरी वाले अलग-अलग शीर्ष युग्मों की संख्या खोजें

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

इसलिए, यदि इनपुट k = 2 है

तो आउटपुट 4 होगा।

समाधान दृष्टिकोण

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

• N := 5005
• graph := आकार N की एडजेसेंसी सूची
• vertex_count := आकार 505 x 5005 का 2D मैट्रिक्स
• res := 0
• insert_edge(x, y) फ़ंक्शन परिभाषित करें:
  • graph[x].append(y)
  • graph[y].append(x)
• dfs(v, parent) फ़ंक्शन परिभाषित करें:
  • vertex_count[v][0] := 1
  • graph[v] में प्रत्येक i के लिए:
    • यदि i != parent:
      • dfs(i, v)
      • j को 1 से k तक:
        • res += vertex_count[i][j-1] * vertex_count[v][k-j]
      • j को 1 से k तक:
        • 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, edges: (1,2), (2,3), (3,4), (2,5)

आउटपुट

4