DFS iterative

dfs_iterative.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct node{
    ll node;
    ll step;
};

ll dfs(map<ll, vector<ll>> &graph, ll startNode, ll endNode) {
    set<ll> visited;
    stack<node> st;
    st.push({startNode, 0});
    ll ans = LLONG_MAX;
    while (!st.empty()) {
        node curNode = st.top();
        st.pop();
        if (curNode.node == endNode) {
            ans = min(ans, curNode.step);
            continue;
        }
        if (visited.count(curNode.node)) continue;
        visited.insert(curNode.node);
        for (ll i : graph[curNode.node]) {
            st.push({i, curNode.step + 1});
        }
    }
    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);
    }
    ll q;
    cin >> q;
    while (q--) {
        ll a, b;
        cin >> a >> b;
        set<ll> visited;
        cout << dfs(graph, a, b) << '\n';
    }
}