【C++】依存関係（前提条件）をもとにすべてのタスクを完了できるか判定するプログラム

本記事では、タスク間の前提条件（依存関係）が与えられたとき、すべてのタスクを完了できるかどうかを判定するC++プログラムについて解説します。

問題の概要

例として、3つのタスクと前提条件 [[1, 0], [2, 1], [3, 2]] が与えられた場合を考えてみましょう。

（[1,0] は「タスク '1' を実行するには、先にタスク '0' を完了しておく必要がある」ことを意味します）

この例では、タスク '0' には前提条件がないため最初に完了できます。次に、タスク '0' が完了しているのでタスク '1' を実行できます。同様に、タスク '2' と '3' も順番に完了できます。したがって、このケースの答えは「True」となります。

アプローチ：グラフとDFSによるサイクル検出

この問題はグラフのアルゴリズムを用いて解くことができます。配列のままではグラフアルゴリズムを適用しにくいため、まずデータをグラフ形式へ変換します。具体的には、「タスク 'n' がタスク 'm' の完了に依存している場合、タスク 'm' からタスク 'n' へ辺を張る」というルールでグラフを構築します。

グラフを作成したら、DFS（深さ優先探索）を利用します。あるノードから出発し、隣接するノード、さらにその隣接ノード…という順に訪問していきます。その過程ですでに訪問中のノードに再び到達した場合、サイクル（循環）が存在することを意味するため、「False」を返します。

一方、末端のノードに到達したら、別の未訪問ノードに対して同じ探索を繰り返します。すべてのノードを訪問できた場合はサイクルが存在しないことになるため、「True」を返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// リストをグラフに変換する
vector<unordered_set<int> > make_graph(int Tasks, vector<pair<int, int> >& dependencies) {
    vector<unordered_set<int> > graph(Tasks);
    for (auto pre : dependencies)
        graph[pre.second].insert(pre.first);
    return graph;
}
// サイクル（巡回）が存在するかチェックする
bool cycle(vector<unordered_set<int> >& graph, int node, vector<bool>& onway, vector<bool>& visited) {
    if (visited[node])
        return false;
    onway[node] = visited[node] = true;
    for (int near : graph[node]) {
        if (onway[near] || cycle(graph, near, onway, visited))
            return true;
    }
    return onway[node] = false;
}
// すべてのタスクを完了できるか判定する
bool canFinish(int Tasks, vector<pair<int, int> >& dependencies) {
    vector<unordered_set<int>>graph = make_graph(Tasks, dependencies);
    vector<bool> onway(Tasks, false), visited(Tasks, false);
    for (int i = 0; i < Tasks; i++) {
        if (!visited[i] && cycle(graph, i, onway, visited))
            return false;
    }
    return true;
}
int main() {
    int Tasks = 6;
    vector<pair<int, int >> dependencies;
    dependencies.push_back(make_pair(1, 0));
    dependencies.push_back(make_pair(2, 1));
    dependencies.push_back(make_pair(3, 2));
    dependencies.push_back(make_pair(5, 3));
    dependencies.push_back(make_pair(4, 5));
    if (canFinish(Tasks, dependencies)) {
        cout << "True";
    }
    else {
        cout << "False";
    }
    return 0;
}

実行結果

True

コードのポイント

• make_graph関数： 依存関係のリストを隣接集合（unordered_set）形式のグラフに変換します。
• cycle関数： DFSでノードを訪問しながら、現在の探索経路上（onway）に再び戻ってきた場合はサイクルありと判定します。
• canFinish関数： 未訪問のノードを起点にサイクル検出を実行し、一つでもサイクルが見つかれば「False」、なければ「True」を返します。

なお、この問題はトポロジカルソート（Kahnのアルゴリズム）を使っても解くことができます。入次数が0のノードから順に取り除いていき、すべてのノードを除去できれば完了可能、途中で除去できなくなるならサイクルが存在すると判定します。