C++で連結リストの連結成分の数を求めるアルゴリズム

問題の概要

重複のない整数値を持つ連結リストの先頭ノード(head)が与えられます。さらに、連結リスト内の値の部分集合であるリストGも渡されます。このとき、Gの中にいくつの「連結成分」が存在するかを求めます。ここで、2つの値が連結しているとは、それらが連結リスト上で連続して現れることを意味します。

例えば、連結リストが [0,1,2,3]、G = [0,1,3] の場合、出力は 2 になります。これは、0と1が連結リスト上で隣接しているため [0,1] という一つの成分となり、3は単独で [3] という別の成分となるからです。

解法のアプローチ

この問題は、連結リストを先頭から順に走査し、「Gに含まれる値の連続した並び(ブロック)」の個数を数えることで解けます。具体的な手順は以下の通りです。

• 答えを格納する ret := 0 で初期化し、集合 s を作成して G のすべての要素を挿入する(高速な検索のため)
• flag := false で初期化する(直前の値がGに含まれていたかどうかを記録)
• head が NULL でない間、以下を繰り返す
  • x := 現在のノードの値
  • s が x を含む場合
    • flag が false なら、ret を 1 増やす(新しい連結成分の始まり)
    • flag := true に設定
  • そうでなければ flag := false に設定
  • head を次のノードへ進める
• 最後に ret を返す

このアルゴリズムのポイントは、「現在の値がGに含まれており、直前の値は含まれていなかった」というタイミングでのみカウントを増やすことです。これにより、各連続ブロックを正確に1回だけ数えることができます。

計算量

連結リストの長さを n、Gのサイズを m とすると、時間計算量は O(n + m)、空間計算量は O(m) となります。非常に効率的なアプローチです。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class ListNode{
   public:
   int val;
   ListNode *next;
   ListNode(int data){
      val = data;
      next = NULL;
   }
};
ListNode *make_list(vector<int> v){
   ListNode *head = new ListNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      ListNode *ptr = head;
      while(ptr->next != NULL){
         ptr = ptr->next;
      }
      ptr->next = new ListNode(v[i]);
   }
   return head;
}
class Solution {
   public:
   int numComponents(ListNode* head, vector<int>& G) {
      int ret = 0;
      set < int > s;
      for(int i = 0; i < G.size(); i++)s.insert(G[i]);
      bool flag = false;
      while(head){
         int x = head->val;
         if(s.count(x)){
            if(!flag) ret++;
            flag = true;
         }else flag = false;
         head = head->next;
      }
      return ret;
   }
};
main(){
   vector<int> v1 = {0,1,2,3};
   vector<int> v2 = {0,1,3};
   ListNode *h1 = make_list(v1);
   Solution ob;
   cout << (ob.numComponents(h1, v2));
}

入力

[0,1,2,3]
[0,1,3]

出力

2

まとめ

本記事では、連結リストと部分集合Gが与えられたときに、G内の連結成分の数を求める問題を扱いました。フラグ変数を使って「連続性の切れ目」を検出するシンプルな走査手法により、O(n + m) の計算量で効率よく解けることを確認しました。連結リストの走査とハッシュ・セットを組み合わせた典型的なパターンなので、類似問題にも応用できる考え方です。