C++で解く「文の類似性 II」：Union-Findを使った効率的な判定アルゴリズム

問題の概要

2つの配列 words1 と words2 が与えられ、それぞれを1つの文とみなします。さらに、類似した単語ペアのリスト pairs も与えられるので、この2つの文が類似しているかどうかを判定するのが本問題です。

例えば、words1 = ["great", "acting", "skills"]、words2 = ["fine", "drama", "talent"] という入力に対して、類似ペアが [["great", "good"], ["fine", "good"], ["acting", "drama"], ["skills", "talent"]] であれば、この2つの文は類似していると判断できます。

類似関係の性質

この問題における類似関係には、次のような重要な性質があります。

• 推移律：「great」と「good」が類似し、「fine」と「good」も類似していれば、「great」と「fine」も類似しているとみなせる。
• 対称性：「great」と「fine」が類似であることは、「fine」と「great」が類似であることと同じ。
• 反射律：どの単語も必ず自分自身と類似している。
• 語数の一致条件：文同士が類似になるのは、両者の単語数が等しい場合のみ。

つまり、この問題はグラフ理論における連結成分の判定として捉えられます。各単語をノード、類似ペアをエッジとみなすと、「2つの単語が類似しているか」は「同じ連結成分に属するか」で判定できます。この種の問題には Union-Find（素集合データ構造）が最適です。

解法のアプローチ

Union-Find を用いて、以下の手順で問題を解きます。

1. 親ノードを管理するマップ parent と、単語に整数IDを割り当てるマップ idx を用意する。
2. getParent(x) 関数を定義する。x が parent に存在しなければ x 自身を返し、存在する場合は再帰的に親を辿りながら経路圧縮を行い、根を返す。
3. unionn(a, b) 関数を定義する。a と b の親をそれぞれ取得し、親が異なる場合のみ一方を他方に統合する。
4. メイン処理では以下を実行する。
   • words1 と words2 のサイズが異なる場合は false を返す。
   • n := words1 のサイズ、counter := 1 で初期化する。
   • words1 の各単語について、idx に未登録なら新しいIDを割り当てる。
   • words2 の各単語についても同様にIDを割り当てる。
   • pairs の各ペア (u, v) について、必要に応じてIDを登録し、unionn(u, v) で統合する。
   • 最後に各位置 i について u = words1[i]、v = words2[i] とし、u == v ならスキップ、getParent(idx[u]) != getParent(idx[v]) なら false を返す。
   • すべてのチェックを通過すれば true を返す。

C++での実装例

以下のコードで実際の動作を確認できます。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   unordered_map<int, int> parent;
   unordered_map<string, int> idx;
   int getParent(int x){
      if (!parent.count(x))
         return x;
      return parent[x] = getParent(parent[x]);
   }
   void unionn(string a, string b){
      int parentA = getParent(idx[a]);
      int parentB = getParent(idx[b]);
      if (parentA == parentB)
         return;
      parent[parentA] = parentB;
   }
   bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<vector<string> >& pairs){
      if (words1.size() != words2.size())
         return false;
      int n = words1.size();
      int counter = 1;
      for (int i = 0; i < n; i++) {
         if (!idx.count(words1[i])) {
            idx[words1[i]] = counter++;
         }
      }
      for (int i = 0; i < n; i++) {
         if (!idx.count(words2[i])) {
            idx[words2[i]] = counter++;
         }
      }
      for (int i = 0; i < pairs.size(); i++) {
         string u = pairs[i][0];
         string v = pairs[i][1];
         if (!idx.count(u)) {
            idx[u] = counter++;
         }
         if (!idx.count(v)) {
            idx[v] = counter++;
         }
         unionn(u, v);
      }
      for (int i = 0; i < n; i++) {
         string u = words1[i];
         string v = words2[i];
         if (u == v)
            continue;
         if (getParent(idx[u]) != getParent(idx[v]))
         return false;
      }
      return true;
   }
};
main(){
   Solution ob;
   vector<string> v = { "great", "acting", "skills" }, v1 = { "fine", "drama", "talent" };
   vector<vector<string> > v2 = { { "great", "good" }, { "fine", "good" }, { "drama", "acting" }, { "skills", "talent" } };
   cout << (ob.areSentencesSimilarTwo(v, v1, v2));
}

入力例

{"great","acting","skills"}, {"fine","drama","talent"},
{{"great","good"},{"fine","good"},{"drama","acting"},{"skills","talent"}}

出力例

1

出力が 1（true）となっており、2つの文が類似していると正しく判定できています。「great」→「good」→「fine」、「acting」→「drama」、「skills」→「talent」という経路で推移的に類似関係が成立しているためです。

計算量について

N を登場する単語の総数、P を類似ペアの数とすると、経路圧縮を適用した Union-Find の各操作はほぼ定数時間（アッカーマン関数の逆関数 α(N)）で完了します。そのため、全体の計算量は O(N + P) 程度に収まり、大規模な入力でも高速に動作します。