Tìm bộ ba sao cho số nút kết nối các bộ ba này là tối đa trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình tìm bộ ba sao cho số lượng nút kết nối các bộ ba này là tối đa.

Đối với điều này, chúng ta sẽ được cung cấp một cây với N nút. Nhiệm vụ của chúng tôi là tìm ra bộ ba nút sao cho các nút được bao phủ trong đường dẫn kết hợp chúng với nhau một cách tối đa.

Ví dụ

#include <bits/stdc++.h>
#define ll long long int
#define MAX 100005
using namespace std;
vector<int> nearNode[MAX];
bool isTraversed[MAX];
//storing the required nodes
int maxi = -1, N;
int parent[MAX];
bool vis[MAX];
int startnode, endnode, midNode;
//implementing DFS to search nodes
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;
      }
   }
}
//finding endnote of diameter
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;
}

Đầu ra

Nodes: (0, 0, 0)