dfs.cpp

#include<bits/stdc++.h>
using namespace std;
vector<int>v[100];
bool visited[100];
int parent[100];

int n,e;
int cyc;

void dfs_visit(int x){
    visited[x]=true;
    for(int i=0;i<v[x].size();i++){
    	int xx = v[x][i];
        if(visited[xx]==false) {
            parent[xx]=x;
            dfs_visit(xx);
        }
    }
    
}

void dfs(){

    for(int i=1;i<=n;i++){
        visited[i]=false;
        parent[i]=NULL;
    }

    for(int i=1;i<=n;i++){
        if(visited[i]==false){
            dfs_visit(i);
        }
    }
}

int main(){


    cin>>n>>e;
    for(int i=0;i<e;i++){
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
    }

    cyc=0;

    dfs();

    if(cyc==1) cout<<"cycle detected\n";

    cout<<"NODE: ";
    for(int i=1;i<=n;i++){
        cout<<i<<" ";
    }

    cout<<"\nPARE: ";
    for(int i=1;i<=n;i++){
        cout<<parent[i]<<" ";
    }
    

}

/*
7 7
1 2
2 1
1 3
2 3
3 4
4 5
6 7
*/