7-2 Depth-first traversal of graphs (15 points)

Hits: 0

[Write a program to perform a depth-first traversal] of a given directed graph (not necessarily connected) , which contains n vertices, numbered 0 to n-1. This question is limited to the depth-first traversal process. If there are multiple vertices to be accessed at the same time, the one with the smallest number is preferentially selected for access, and vertex 0 is the starting point of the traversal.

Input format:
The first line of input is two integers n and e, which represent the number of vertices and edges of the graph respectively, where n does not exceed 20000 and e does not exceed 50. The next line e represents the information of each edge, each line has two integers a and b, which represent the endpoint number of the edge, but the edges are not arranged in the order of endpoint numbers.

Output format:
The output is a line of integers, each integer is followed by a space, that is, the depth-first traversal node sequence of the directed graph.

Input format:
3 3
0 1
1 2
0 2

Output format:
0 1 2

Input format:
4 4
0 2
0 1
1 2
3 0

Output format:
0 1 2 3

#include<iostream>
#include<string.h>
#include<vector>
#include<queue>
#include <algorithm>
using namespace std;
vector<int> a[20010];
int visit[20010]; 
int n,e,sum;
void dfs(int cur){
    int i;
    cout<<cur<<" ";
    visit[cur] = 1;
    int len = a[cur].size();
    //if(sum==n) return ;
    for(int i = 0;i<len;i++){
        //printf("size = %d\n",a[i].size());
        if (visit[a[cur][i]]==0)
        {
            //visit[i] = 1;
            dfs(a[cur][i]);
            //sum++;
        }                                                                                                    
    }
    //cout<<cur<<" ";
    //return ; 
}
int main(){

    int b1,b2;
    cin>>n>>e;

    for(int i = 0;i<e;i++){
        cin>>b1>>b2;
        a[b1].push_back(b2);
    }

    for(int i = 0;i<n;i++){
        sort(a[i].begin(),a[i].end());
    }

    //visit[0] = 1; //The first node has been visited 
    for ( int i = 0 ;i<n;i++){
         if (visit[i] == 0 ){
            dfs(i);
        }
    }
    return 0; 
}

You may also like...

Leave a Reply

Your email address will not be published.