dfsの疑問点

経緯

敬遠していた，グラフ問題に対する有効的で基礎的なアルゴリズムであるdfs(depth-first-search)の苦手意識の払拭のため練習を行うことにした

解いた問題

• ABC054 C - One-stroke Path
  頂点1を始点とした全頂点経由経路の数を求める
• ABC075 C - Bridge
  連結なグラフが渡され，辺を消すとグラフ全体が非連結になる辺の数を求める

疑問点

先人のコードを見ながら書いていたら通過済みの頂点の扱いについて悩んだ
以下にACしたコードを載せる

• One-stroke Path

#include <bits/stdc++.h>
using namespace std;

int n, m, ans, vc;
int G[10][10];
bool used[10];

void dfs(int now){
    used[now] = true;
    vc++;
    if(vc == n){
        ans++;
    }
    for(int i = 0; i < n; i++){
        if(!used[i] && G[now][i]){
            dfs(i);
        }
    }
    used[now] = false;
    vc--;
    return;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a][b] = true;
        G[b][a] = true;
    }

    dfs(0);

    cout << ans << endl;

    return 0;
}

• Bridge

#include <bits/stdc++.h>
using namespace std;

int n, m;
const int MAX = 55;
int A[MAX], B[MAX];
bool G[MAX][MAX], used[MAX];

void dfs(int now){
    used[now] = true;
    for(int i = 0; i < n; i++){
        if(!used[i] && G[now][i]){
            dfs(i);
        }
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
        G[A[i]][B[i]] = true;
        G[B[i]][A[i]] = true;
    }

    int ans = 0;
    for(int i = 0; i < m; i++){
        G[A[i]][B[i]] = false;
        G[B[i]][A[i]] = false;

        for(int j = 0; j < n; j++){
            used[j] = false;
        }

        dfs(0);

        bool bridge = false;
        for(int j = 0; j < n; j++){
            if(used[j] == false) bridge = true; 
        }
        if(bridge) ans++;

        G[A[i]][B[i]] = true;
        G[B[i]][A[i]] = true;
    }

    cout << ans << endl;

    return 0;
}

疑問が浮かんだのは以下の部分

• One-stroke Path

void dfs(int now){
    used[now] = true;
    vc++;
    if(vc == n){
        ans++;
    }
    for(int i = 0; i < n; i++){
        if(!used[i] && G[now][i]){
            dfs(i);
        }
    }
    used[now] = false;
    vc--;
    return;
}

• Bridge

void dfs(int now){
    used[now] = true;
    for(int i = 0; i < n; i++){
        if(!used[i] && G[now][i]){
            dfs(i);
        }
    }
}

疑問点はBridgeのdfs関数内で頂点の通過状態をfalseにしないこと
Bridgeはm本の辺をそれぞれ抜いた状態でdfsをする
なんとなくは分かるが言語化ができない…

おわりに

謎が謎を呼ぶ