C++ですべての電球を点灯できるかどうかを判定する方法

この記事では、m個の電球とn個のスイッチが与えられたとき、すべての電球を点灯できるかどうかを判定するC++プログラムを紹介します。

問題の概要

数値 m と、n 個のサブリストからなるネストされたリスト A があるとします。全部で m 個の電球があり、初期状態ではすべて消えています。n 個のスイッチが存在し、それぞれがいくつかの電球に接続されています。A[i] は「i 番目のスイッチを押すことで点灯できる電球の集合」を表します。このとき、すべての電球を点灯できるかどうかを確認する必要があります。

例えば、入力が A = [[1, 4], [1, 3, 1], [2]]、m = 4 の場合、出力は True（1）になります。すべてのスイッチを押せば、4つの電球すべてを点灯できるからです。

解法のアプローチ

この問題は非常にシンプルで、以下の手順で解くことができます。

• 空の集合（set）s を定義する。
• リスト A の各要素を走査し、含まれるすべての電球番号を s に挿入する。
• s のサイズが m と一致すれば true を返し、そうでなければ false を返す。

set は重複を自動的に排除してくれるため、複数のスイッチが同じ電球に接続されていても問題ありません。最終的に集合に含まれる電球の種類数が m と一致していれば、全電球を点灯可能だと判断できます。

擬似コード

Define one set s
for initialize i := 0, when i < size of A, update (increase i by 1), do:
    for initialize j := 0, when j < size of A[i], update (increase j by 1), do:
        insert A[i, j] into s
if size of s is same as m, then:
    return true
Otherwise
    return false

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<vector<int>> A, int m){
    set<int> s;
    for (int i = 0; i < A.size(); i++){
        for (int j = 0; j < A[i].size(); j++){
            s.insert(A[i][j]);
        }
    }
    if (s.size() == m)
        return true;
    else
        return false;
}
int main(){
    vector<vector<int>> A = { { 1, 4 }, { 1, 3, 1 }, { 2 } };
    int m = 4;
    cout <<solve(A, m) << endl;
}

実行結果

入力

{ { 1, 4 }, { 1, 3, 1 }, { 2 } }, 4

出力

1

出力が 1（true）となり、すべてのスイッチを押すことで4つの電球すべてを点灯できることが確認できました。

計算量について

このアルゴリズムの時間計算量は O(N) です。ここで N はリスト A に含まれる全要素数の合計です。set への挿入は平均 O(log k)（k は集合のサイズ）ですが、全体としては要素数に比例した計算量で処理できます。空間計算量も O(m) となり、非常に効率的な解法といえます。