इस ट्यूटोरियल में, हम ट्रिपलेट खोजने के प्रोग्राम पर चर्चा करेंगे जिससे इन ट्रिपलेट्स को जोड़ने वाले नोड्स की संख्या अधिकतम हो।
इसके लिए हमें N नोड्स वाला एक ट्री प्रदान किया जाएगा। हमारा कार्य नोड्स का एक ट्रिपलेट खोजना है जिससे उन्हें जोड़ने वाले पथ में नोड्स की संख्या अधिकतम हो।
उदाहरण
#include <bits/stdc++.h> #define ll long long int #define MAX 100005 using namespace std; vector<int> nearNode[MAX]; bool isTraversed[MAX]; //आवश्यक नोड्स संग्रहीत करना int maxi = -1, N; int parent[MAX]; bool vis[MAX]; int startnode, endnode, midNode; //नोड्स खोजने के लिए DFS लागू करना void performDFS(int u, int count) { isTraversed[u] = true; int temp = 0; for (int i = 0; i < nearNode[u].size(); i++) { if (!isTraversed[nearNode[u][i]]) { temp++; performDFS(nearNode[u][i], count + 1); } } if (temp == 0) { if (maxi < count) { maxi = count; startnode = u; } } } void performDFS2(int u, int count) { isTraversed[u] = true; int temp = 0; for (int i = 0; i < nearNode[u].size(); i++) { if (!isTraversed[nearNode[u][i]] && !vis[nearNode[u][i]]) { temp++; performDFS2(nearNode[u][i], count + 1); } } if (temp == 0) { if (maxi < count) { maxi = count; midNode = u; } } } //व्यास के एंडनोड को खोजना void performDFS1(int u, int count) { isTraversed[u] = true; int temp = 0; for (int i = 0; i < nearNode[u].size(); i++) { if (!isTraversed[nearNode[u][i]]) { temp++; parent[nearNode[u][i]] = u; performDFS1(nearNode[u][i], count + 1); } } if (temp == 0) { if (maxi < count) { maxi = count; endnode = u; } } } void calcTreeVertices() { performDFS(1, 0); for (int i = 0; i <= N; i++) isTraversed[i] = false; maxi = -1; performDFS1(startnode, 0); for (int i = 0; i <= N; i++) isTraversed[i] = false; int x = endnode; vis[startnode] = true; while (x != startnode) { vis[x] = true; x = parent[x]; } maxi = -1; for (int i = 1; i <= N; i++) { if (vis[i]) performDFS2(i, 0); } } int main() { N = 4; nearNode[1].push_back(6); nearNode[2].push_back(0); nearNode[1].push_back(7); nearNode[3].push_back(0); nearNode[1].push_back(2); nearNode[4].push_back(0); calcTreeVertices(); cout << "Nodes: (" << startnode << ", " << endnode << ", " << midNode << ")"; return 0; } आउटपुट
Nodes: (0, 0, 0)
