グラフ内のスーパー頂点を見つけるC++プログラムの解説

問題の概要

n個の頂点を持つグラフが与えられていると仮定しましょう。頂点には1からnまでの番号が付けられており、配列「edges」に含まれる辺によって互いに接続されています。さらに、各頂点は1からnの範囲の数値である「x」という値を持ち、その値は配列「values」で与えられます。

このとき、グラフの中から「スーパー頂点(super vertex)」と呼ばれる特別な頂点を見つけ出す必要があります。頂点iがスーパー頂点であるとは、頂点1から頂点iへの最短経路上に、i番目の頂点と同じ「x」の値を持つ頂点が存在しないことを意味します。この条件を満たすすべての頂点を出力してください。

たとえば、入力が n = 5、values = {1, 2, 2, 1, 3}、edges = {{1, 2}, {2, 3}, {2, 3}, {2, 4}, {4, 5}} の場合、出力は「1 3 4 5」になります。

このケースでは、頂点2以外のすべての頂点が条件を満たしているため、頂点2だけが出力から除外されます。

アルゴリズムの手順

この問題は深さ優先探索(DFS)を使うことで効率的に解くことができます。頂点1から探索を開始し、現在の経路上に出現済みの値を頻度配列で管理することで、各頂点がスーパー頂点かどうかを判定します。具体的な手順は以下の通りです。

サイズ100005の配列 vertexVal、frq、chk を定義する。
サイズ200005の配列 vcti を定義する。
関数 dfs(j, k) を定義する。
    もし frq[vertexVal[j]] が 0 ならば:
        chk[j] := 1
    frq[vertexVal[j]] を1増やす
    vcti[j] 内の各要素 a について:
        a が k と等しくなければ:
            dfs(a, j) を呼び出す
    frq[vertexVal[j]] を1減らす
i := 0 から n 未満の間、i を1ずつ増やしながら:
    vertexVal[i] := values[i]
i := 0 から n 未満の間、i を1ずつ増やしながら:
    a := edges[i] の始点
    b := edges[i] の終点
    vcti[a] の末尾に b を追加する
    vcti[b] の末尾に a を追加する
dfs(1, 0) を呼び出す
i := 1 から n 以下の間、i を1ずつ増やしながら:
    chk[i] が 0 以外ならば:
        i を出力する

ポイント解説

配列 frq は「頂点1から現在注目している頂点までの経路上に、各値が何回出現したか」を記録しています。ある頂点へ到達した時点で、その頂点の値がまだ一度も出現していなければ(frq の値が 0 であれば)、その頂点はスーパー頂点として chk 配列にマークされます。再帰から抜ける際にカウントを減らすことで、経路情報を正しく維持できるのがポイントです。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;

int n;
int vertexVal[100005], frq[100005], chk[100005];
vector<int> vcti[200005];

void dfs(int j, int k){
    if (frq[vertexVal[j]] == 0)
        chk[j] = 1;
    frq[vertexVal[j]]++;
    for (auto a : vcti[j]) {
        if (a != k)
            dfs(a, j);
    }
    frq[vertexVal[j]]--;
}
void solve(int values[], vector<pair<int, int>> edges){
    for (int i = 0; i < n; i++)
        vertexVal[i] = values[i];
    for (int i = 0; i < n; i++){
        int a, b;
        a = edges[i].first;
        b = edges[i].second;
        vcti[a].push_back(b);
        vcti[b].push_back(a);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++){
        if (chk[i]) cout << i << endl;
    }
}
int main() {
    n = 5;
    int values[] = {1, 2, 2, 1, 3};
    vector<pair<int, int>> edges = {{1, 2}, {2, 3}, {2, 3}, {2, 4}, {4, 5}};
    solve(values, edges);
    return 0;
}

入力例

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

出力例

1
3
4
5

まとめ

本記事では、DFSを用いてグラフ内のスーパー頂点を効率的に検出するC++プログラムを紹介しました。経路上の値の出現回数を頻度配列で管理するというシンプルな発想により、各頂点が条件を満たすかどうかを高速に判定できるのが魅力です。グラフ探索と再帰の組み合わせに慣れたい方にとって、良い練習題材となるでしょう。