C++でグラフが有効な木（ツリー）であるかを判定する方法

n個のノードが0からn-1までのラベルで与えられ、無向辺のリスト [u, v] があるとします。これらの辺が有効な木（ツリー）を構成しているかどうかを判定する関数を定義する必要があります。

例えば、入力が n = 5、edges = [[0,1], [0,2], [0,3], [1,4]] の場合、出力は true になります。

解決のためのアプローチ

この問題は、深さ優先探索（DFS）を用いて解くことができます。グラフが木であるためには、次の2つの条件を満たす必要があります。

• 閉路（サイクル）が存在しないこと
• すべてのノードが連結していること

DFSの実行中に各ノードの状態を visited 配列で管理します。0は未訪問、2は探索中、1は探索完了（有効）を表します。

dfs() 関数の定義

dfs() 関数は、node（現在のノード）、par（親ノード）、graph（隣接リスト）、visited（訪問状態を記録する配列）を受け取ります。

• visited[node] が 1 の場合 → true を返す
• visited[node] が 2 の場合 → false を返す（閉路を検出したことを意味します）
• visited[node] := 2 とする
• ret := true とする
• i := 0 から graph[node] のサイズ未満の間、以下を繰り返す：
  • graph[node][i] が par と等しくない場合 → ret := ret AND dfs(graph[node][i], node, graph, visited)
• visited[node] := 1 とする
• ret を返す

メイン処理の流れ

• サイズ n の配列 visited を定義し、0で初期化する
• サイズ n の隣接リスト graph を定義する
• i := 0 から edges のサイズ未満の間、以下を繰り返す：
  • u := edges[i][0]、v := edges[i][1]
  • graph[u] の末尾に v を追加する
  • graph[v] の末尾に u を追加する
• dfs(0, -1, graph, visited) が false の場合 → false を返す
• i := 0 から n 未満の間、以下を繰り返す：
  • visited[i] が 0 の場合 → false を返す（連結していないノードが存在することを意味します）
• true を返す

実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool dfs(int node, int par, vector<int> graph[], vector<int>& visited){
        if (visited[node] == 1)
            return true;
        if (visited[node] == 2)
            return false;
        visited[node] = 2;
        bool ret = true;
        for (int i = 0; i < graph[node].size(); i++) {
            if (graph[node][i] != par)
                ret &= dfs(graph[node][i], node, graph, visited);
        }
        visited[node] = 1;
        return ret;
    }
    bool validTree(int n, vector<vector<int>>& edges) {
        vector<int> visited(n, 0);
        vector<int> graph[n];
        for (int i = 0; i < edges.size(); i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        if (!dfs(0, -1, graph, visited))
            return false;
        for (int i = 0; i < n; i++) {
            if (!visited[i])
                return false;
        }
        return true;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{0,1},{0,2},{0,3},{1,4}};
    cout << (ob.validTree(5,v));
}

入力

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

出力

1

出力が 1（true）となり、与えられた辺の集合が有効な木を構成していることが確認できます。このアルゴリズムでは、DFSによって閉路の有無を検出しつつ、探索後にすべてのノードが訪問済み（visited[i] != 0）であることを確認することで、グラフ全体の連結性も同時にチェックしています。