algorithm - Finding bridges in graph without recursion -

i have code find bridges in connected graph:

void dfs (int v, int p = -1) {     used[v] = true;     tin[v] = fup[v] = timer++;     (size_t i=0; i<g[v].size(); ++i) {         int = g[v][i];         if (to == p)  continue;         if (used[to])             fup[v] = min (fup[v], tin[to]);         else {             dfs (to, v);             fup[v] = min (fup[v], fup[to]);             if (fup[to] > tin[v])                 printf("%d %d", v, to);         }     } } 

how rewrite without using recursion? know, it's possible , should use stack, line must executed after recursive call of dfs() , can't achieve stack:

fup[v] = min(fup[v], fup[to]) 

so, how rewrite algorithm iteratively?

you want make "stack frame" structure

struct frame {     frame(int v, int p, int i, label label);     int v;     int p;     int i; };  // constructor here 

and, say, stack<frame>. between of these fields, it's possible simulate call stack (untested code give general idea).

void dfs(int v, int p = -1) {   stack<frame> st;   st.push(frame(v, p, 0));   {     frame fr(st.top());     st.pop();     v = fr.v;     p = fr.p;     int i(fr.i);     if (i > 0) {       int to(g[v][i - 1]);       fup[v] = min(fup[v], fup[to]);       if (fup[to] > tin[v]) { printf("%d %d", v, to); }       if (i == g[v].size()) { continue; }     } else if (i == 0) {       used[v] = true;       tin[v] = fup[v] = timer++;     }     int to(g[v][i]);     if (to == p) { continue; }     if (used[to]) {        fup[v] = min(fup[v], tin[to]);     } else {        st.push(frame(to, v, 0));     }     st.push(frame(v, p, + 1));   } while (!st.empty()); }