dfs

#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>


using namespace std;

#define MAXN 1000

int N, M;
int G[MAXN][MAXN] = { 0 };
int U[MAXN+1], S[MAXN], P[MAXN],T[MAXN],top, t;
void empty_stack() { top = -1; }
void push(int x) { S[++top] = x; }
void pop() { top--; }
int look() { return S[top]; }
bool not_empty() { return top > -1; }


void DFS(int r)
{
    for (int i = 1; i <= N; i++) U[i] = 0;
    empty_stack();
    push(r); U[r] = 1; P[r] = 0;
    while (not_empty())
    {
        int t = look(); if (G[t][0] > 0)
        {
            int v = G[t][G[t][0]--];
            if (!U[v]) { U[v] = 1; P[v] = t; push(v); }
        }
        else pop();
    }
}
void DFS_R(int r)
{
    int y;
    while (G[r][0] > 0)
    {
        y = G[r][G[r][0]--];
        if (!U[y]) { U[y] = 1; P[y] = r; DFS_R(y); }
    }
    T[t--] = r;

}
void first_call()
{
    int i; for (i = 1; i <= N; i++) U[i] = 0; t = N - 1;
    for (i = 1; i <= N; i++) if (U[i] == 0)
    {
        U[i] = 1; P[i] = 0; DFS_R(i);
    }
}

void DFS_R_keepCounters(int r)
{
    int y;
    while (G[0][r] > 0)
    {
        y = G[r][G[0][r]--];
        if (!U[y]) { U[y] = 1; P[y] = r; DFS_R(y); }
    }
}
void first_call_keepCounters() {
    int I;
    for (int i = 1; i <= N; i++) { U[i] = 0; G[0][i] = G[i][0]; }
    for (int i = 1; i <= N; i++) if (U[i] == 0)
    {
        U[i] = 1; P[i] = 0; DFS_R(i);
    }
}


int main()
{
    int i, u, v;

        scanf_s("%d %d", &N, &M);


        for (i = 1; i <= M; i++) {
            scanf_s("%d %d", &u, &v);
            G[u][++G[u][0]] = v;
            G[v][++G[v][0]] = u;
        }

        //cout << M <<" "<< N << endl;

        //for (int i = 1; i <= N; i++)
        //{
        //  for (int j = 0; j <= N; j++)
        //  {
        //      cout << G[i][j] << " ";
        //  }
        //  cout << endl;
        //}

        cout << "Iterative DFS" << endl;
        DFS(1);

        for (size_t i = 0; i < N; i++)
        {
            cout << S[i] << endl;
        }
        cout << "Now recursive:" << endl;

        first_call();
        for (size_t i = 0; i < N; i++)
        {
            cout << S[i] << endl;
        }

        cout << "Now keeping the counters:" << endl;

        first_call_keepCounters();
        for (size_t i = 0; i < N; i++)
        {
            cout << S[i] << endl;
        }

        cout << "Topologic:" << endl;

        first_call();
        for (size_t i = 0; i < N; i++)
        {
            cout << T[i] << endl;
        }

}