C++でグラフ内のシンクノードの数を効率的に求める方法

本記事では、グラフに含まれるシンクノード（沈み込みノード）の数を求める問題について、その考え方と具体的な解法を詳しく解説します。

まず問題設定を確認しましょう。N個のノード（1からNまで）とM個のエッジを持つ有向非巡回グラフ（DAG: Directed Acyclic Graph）が与えられます。このとき、グラフ内に存在するシンクノードの総数を求めることが目標です。

シンクノードとは、出ていくエッジ（出力辺）を一切持たないノードのことです。つまり、そのノードから他のノードへ向かう矢印が1本も存在しないノードを指します。

入力例と出力例

入力：n = 4, m = 2

Edges[] = {{2, 3}, {4, 3}}
出力：2

この例では、ノード2から3へ、ノード4から3へエッジが張られています。出力エッジを持たないのはノード1とノード3の2つなので、答えは2となります。

シンプルな解法アプローチ

最も直感的な解き方は次の通りです。

1. グラフのすべてのエッジを走査する。
2. エッジの出発元となるノード（始点）を集合（set）に格納していく。setは重複を自動的に排除するため、出力エッジを持つ「異なるノード」だけが残る。
3. 全ノード数から set のサイズ（＝シンクではないノードの数）を引けば、それがシンクノードの数になる。

この方法なら、シンクかどうかを各ノードごとに個別に判定する必要がなく、エッジ情報だけで一発的に答えを導き出せます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n = 4; // ノードの数
    int m = 2; // エッジの数
    vector<pair<int, int>> edges = {{2, 3}, {4, 3}}; // first から second へ向かうエッジ
    set<int> s;
    for(int i = 0; i < m; i++){
        s.insert(edges[i].first); // 出力エッジを持つノードを重複なく記録
    }
    cout << n - s.size(); // 全ノード数 - シンクでないノード数 = シンクノード数
    return 0;
}

実行結果

2

コードの解説

このコードでは、まず edges ベクトルを走査し、各ペアの最初の要素（エッジの始点）を set に挿入しています。set は重複した値を保持しないため、走査が終わった時点で set には「出力エッジを持つ異なるノード」のみが格納されています。

あとは全ノード数 n から set のサイズを引くことで、出力エッジを持たないノード、すなわちシンクノードの数が求まります。

計算量について見てみましょう。エッジを1回ずつ走査し、set への挿入は平均 O(log M) で行えるため、全体の計算量は O(M log M) です（Mはエッジ数）。エッジ数がノード数より十分小さい場合や、ハッシュセット（unordered_set）を使えば O(M) に近づけることもできます。これは非常に効率的なアプローチです。

補足：隣接リストを使った別解

もう少し汎用的な方法として、各ノードの出次数（out-degree）を配列で管理する手法もあります。すべてのエッジ (u, v) に対して outDegree[u] をインクリメントし、最後に outDegree が 0 のノードを数えれば、それがシンクノードの数です。こちらも計算量は O(N + M) となり、グラフの構造を保持したい場合に便利です。

まとめ

本記事では、set を活用することでグラフ内のシンクノードの数を効率的に求める方法を紹介しました。ポイントは「出力エッジの始点を重複なく記録し、全ノード数から差し引く」というシンプルな発想です。同じロジックは C言語、Java、Python など他のプログラミング言語でも容易に実装できます。アルゴリズムの練習やコーディング試験の対策として、ぜひ参考にしてください。