C++で公約数をもとにグラフの最大連結成分サイズを求める方法

問題の概要

互いに異なる正整数からなる配列 A が与えられたとします。ここで、次のようなグラフを考えてみましょう。

グラフのノード数は配列 A の長さと同じで、各ノードには A[0] から A[A のサイズ − 1] までのラベルが付いています。A[i] と A[j] が 1 より大きい共通の約数(公約数)を持つとき、A[i] と A[j] の間に辺が張られます。この課題では、グラフ内の最大連結成分のサイズを求めることが目標です。

たとえば、入力が [4, 6, 15, 35] の場合、出力は 4 になります。これは、4 と 6 が公約数 2 を、6 と 15 が公約数 3 を、15 と 35 が公約数 5 を共有しており、すべてのノードが 1 つの連結成分につながるためです。

解法のアプローチ

この問題は、Union-Find(素集合データ構造)を使うことで効率的に解けます。各要素を素因数分解し、同じ素因数を持つ要素同士を順次統合していくのがポイントです。具体的には、以下の手順で進めます。

getParent() 関数

• parent[x] が -1 と等しい場合は、x をそのまま返します。
• それ以外の場合は、parent[x] = getParent(parent[x]) を返します(経路圧縮によって木構造を平坦化し、探索を高速化します)。

unionn() 関数(x と y を引数に取る)

• parX := getParent(x)、parY := getParent(y) を求めます。
• parX と parY が等しい場合は、すでに同じグループなので何もせずに戻ります。
• rank[parX] ≥ rank[parY] の場合は、rank[parX] := rank[parX] + rank[parY] とし、parent[parY] := parX とします。
• それ以外の場合は、rank[parY] := rank[parY] + rank[parX] とし、parent[parX] := parY とします。

main メソッドでの処理

• ret := 0、n := 配列 A のサイズ とします。
• parent := サイズ n の配列を作成し、すべて -1 で初期化します。
• rank := サイズ n の配列を作成し、すべて 1 で初期化します。
• 「約数 → 要素インデックス」を記録するためのマップ m を定義します。
• i := 0 から n 未満の間、i を 1 ずつ増やしながら次を実行します。
  • x := A[i] とします。
  • j := 2 から j × j ≤ x の間、j を 1 ずつ増やしながら次を実行します。
    • x mod j が 0 の場合(j が x の約数の場合):
      • m に j が既に存在すれば unionn(m[j], i) を呼び出し、存在しなければ m[j] := i と登録します。
      • 同様に、m に x / j が存在すれば unionn(m[x / j], i) を呼び出し、存在しなければ m[x / j] := i と登録します。
  • 試し割りループの後、m に x 自身が存在すれば unionn(m[x], i) を呼び出し、存在しなければ m[x] := i と登録します。
  • ret := max(ret, rank[getParent(i)]) として、現在の最大連結成分サイズを更新します。
• 最後に ret を返します。

理解を深めるために、以下の実装例を見てみましょう。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    vector<int> parent;
    vector<int> rank;
    int getParent(int x){
       if (parent[x] == -1)
       return x;
       return parent[x] = getParent(parent[x]);
    }
    void unionn(int x, int y){
       int parX = getParent(x);
       int parY = getParent(y);
       if (parX == parY)
       return;
       if (rank[parX] >= rank[parY]) {
          rank[parX] += rank[parY];
          parent[parY] = parX;
       } else {
          rank[parY] += rank[parX];
          parent[parX] = parY;
       }
    }
    int largestComponentSize(vector<int>& A) {
       int ret = 0;
       int n = A.size();
       parent = vector<int>(n, -1);
       rank = vector<int>(n, 1);
       unordered_map<int, int> m;
       for (int i = 0; i < n; i++) {
          int x = A[i];
          for (int j = 2; j * j <= x; j++) {
             if (x % j == 0) {
                if (m.count(j)) {
                   unionn(m[j], i);
                } else {
                   m[j] = i;
                }
                if (m.count(x / j)) {
                   unionn(m[x / j], i);
                } else {
                   m[x / j] = i;
                }
             }
          }
          if (m.count(x)) {
             unionn(m[x], i);
          } else {
             m[x] = i;
          }
          ret = max(ret, rank[getParent(i)]);
       }
       return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {4,6,15,35};
    cout << (ob.largestComponentSize(v));
}

入力

{4,6,15,35}

出力

4

計算量の目安

各要素に対して √x まで試し割りを行うため、時間計算量は要素数を n、配列内の最大値を M としたとき O(n・√M) 程度になります。加えて Union-Find の統合操作はほぼ定数時間で処理できるため、全体として非常に効率的です。空間計算量は parent・rank・マップの分だけ必要となり、O(n) です。