Recursive DFS

dfs_recursive.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll dfs(map<ll, vector<ll>> &graph, ll curNode, ll endNode, ll step = 0, set<ll> &visited) {
    if (curNode == endNode) return step;
    if (visited.count(curNode)) return -1;
    visited.insert(curNode);
    ll ans = LLONG_MAX;
    for (ll i : graph[curNode]) {
        ll x = dfs(graph, i, endNode, step + 1, visited);
        if (x == -1) continue;
        ans = min(ans, x);
    }
    return ans;
}

int main() {
    ll n;
    cin >> n;
    map<ll, vector<ll>> graph;
    while (n--) {
        ll a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    ll q;
    cin >> q;
    while (q--) {
        ll a, b;
        cin >> a >> b;
        set<ll> visited;
        cout << dfs(graph, a, b, visited) << '\n';
    }
}