【ABC285_D】 DFS(深さ優先探索)で解いてみた 【C++】

abc285のD問題をDFS(深さ優先探索)を使って解いてみました。
言語はC++です。

• UnionFindを使った解き方はこちら
• BFS(幅優先探索)を使った解き方はこちら

Point

1. a → b → c → aと一巡したらダメそう
   • グラフ理論でいうところのサイクル(閉路)があるかどうかを検出
2. 探索した頂点をmemoすることでTLE対策
3. DFS(深さ優先探索)で全頂点から探索してサイクルがあるかを検出
   • 既にvisitedな頂点に再度訪問 -> サイクル有り

      a------>b------>c　　 既に訪問済みの頂点aに対し、aに再訪問するとサイクルができる
      ^---２回目のa---|
   

4. 解けました！

コード例

d_dfs.cpp

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, a, b) for (int i = a; i < b; i++)

int n;
unordered_map<string, bool> memo;
unordered_map<string, int> visited;
using Graph = unordered_map<string, vector<string>>;
Graph G;

bool dfs(string s){
    memo[s] = true; //探索した全頂点を記録
    if(visited[s]) return true; //既に行きがけで探索済みの頂点に再度訪れた場合、サイクルが出来ているのでtrue
    //ex. a---->b---->c---->aは  最初のaでvisited[a]=trueなので、
    //    a---->b---->c 二回目のaではサイクルができる
    //    ^-----------|
    bool closed = false;
    //行きがけの往路だけtrueにしておく
    //a----->b  visited[b] = true;
    visited[s] = true;
    for(auto t : G[s]){
        if(dfs(t)) closed = true;
    }
    //行きがけの復路はfalse
    //a----->b  visited[b] = false;
    //^------| return
    visited[s]=false;
    return closed;
}

int main(){
    cin>>n;
    vector<string> s(n), t(n);
    rep(i,0,n){
        cin >> s[i] >> t[i];
        //s->tのグラフを作成
        G[s[i]].emplace_back(t[i]);
    }
    rep(i,0,n){
        string start = s[i];
        if(memo[start]) continue;  //既にdfsで探索済み頂点は無視
        bool closed = dfs(start);
        if(closed){
            cout << "No" << endl; 
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

解けました！