dfs的递归与非递归

#include "iostream"

using namespace std;

const int N = 1e5 + 10;

int h[N], ne[N], e[N], idx;
bool st[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs1(int u){
    st[u] = 1;
    cout << u << endl;
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];

        if(!st[j])dfs1(j);
    }
}

void dfs2(int u){
    int stk[N], tt = 0;
    st[u] = 1;
    stk[++tt] = u;
    cout << u << endl;
    while(tt){
        u = stk[tt--];
        for(int i = h[u]; i != -1; i = ne[i]){
            int j = e[i];
            if(!st[j]){
                st[j] = 1;
                stk[++tt] = u;
                stk[++tt] = j;
                cout << j << endl;
                break;
            }
        }
    }
}

int main(){
    memset(h, -1, sizeof h);
    add(1,6);
    add(1, 2);
    add(2, 3);
    add(2, 5);
    add(3, 4);
    add(4, 5);
    add(5, 6);
    add(6, 7);
    add(6, 8);
    dfs1(1);
    cout << "..."<<endl;
    memset(st, 0, sizeof st);
    dfs2(1);
    return 0;
}