C++で接続するノード数が最大となるトリプレット（3つのノードの組）を見つける方法

はじめに

このチュートリアルでは、木構造において「3つのノード（トリプレット）を結ぶパス上に含まれるノードの数」が最大となるようなトリプレットを見つけるプログラムについて解説します。

N個のノードからなる木が与えられ、その中から3つのノードを選びます。選んだノード同士を結ぶパス全体で覆われるノードの数が最大になるような組み合わせを見つけることが、この記事のゴールです。

アルゴリズムのアプローチ

この問題は、木の「直径」（任意の2ノード間で最も長くなる経路）を求めるテクニックを応用することで効率的に解けます。具体的な手順は次の通りです。

1. 任意のノードからDFS（深さ優先探索）を行い、最も遠くにあるノードを起点（startnode）として記録します。
2. その起点から再度DFSを行い、最も遠くにあるノードを終点（endnode）として記録します。この2点間の経路が木の直径となります。
3. 直径を構成するすべてのノードを訪問済みとしてマークします。
4. 直径上の各ノードから3回目のDFSを行い、直径に含まれない最も遠いノードを中間ノード（midNode）として記録します。

こうして得られる3つのノード（startnode、endnode、midNode）こそが、接続されるノード数を最大化するトリプレットです。

C++による実装例

#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)

まとめ

本記事では、DFSを3回使ってまず木の直径を求め、そこから伸びる最長の分岐を特定することで、パス上に含まれるノード数が最大となるトリプレットを見つける方法を紹介しました。木の直径を求める手法は競技プログラミングなどでも頻出のテクニックなので、ぜひ理解を深めておきましょう。