深さ優先探索_DFS - meruneru/tech_memo GitHub Wiki

概要

スタックに積んで、グラフを深さ方向に潜って探索する。

適用できる問題

SからTへ到達できるか

#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;

// 深さ優先探索
vector<bool> seen;
void dfs(const Graph &G, int v) {
    seen[v] = true; // v を訪問済にする

    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue; // next_v が探索済だったらスルー
        dfs(G, next_v); // 再帰的に探索
    }
}

int main() {
    // 頂点数と辺数、s と t
    int N, M, s, t; cin >> N >> M >> s >> t;

    // グラフ入力受取
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
    }

    // 頂点 s をスタートとした探索
    seen.assign(N, false); // 全頂点を「未訪問」に初期化
    dfs(G, s);

    // t に辿り着けるかどうか
    if (seen[t]) cout << "Yes" << endl;
    else cout << "No" << endl;
}

参考サイト

https://qiita.com/drken/items/4a7869c5e304883f539b

⚠️ **GitHub.com Fallback** ⚠️