fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int MAX = 100010; 
  4. int degree[MAX];                  // keep track of degree of each node , then take it's cumulative sum
  5. int copy_of_prefix[MAX];          // copy of cumulative sum of degree's 
  6. int edges[2 * MAX][2];            // store edges 
  7. int graph[4 * MAX];               // store graph infomartion 
  8. int visit[MAX];                   // visit array  used in Dfs
  9. void dfs(int node){           
  10.   visit[node] = 1;
  11.   cout << node <<" ";             //  print nodes in dfs order 
  12.   for(int i = degree[node - 1] ; i < degree[node] ; ++i ){         // For loop for index of adjacent nodes to node which are present in graph array
  13.      int to = graph[i];                                        
  14.       if(!visit[to])
  15.       dfs(to);
  16.   }
  17. }
  18. int main(){
  19.               int Node , Edge;
  20.               cin >> Node >> Edge;                         // Node = total nodes present in graph , Edge = total edges
  21.               for(int i = 1 ; i <= Edge; ++i ){
  22.                 int u , v;
  23.                 cin >> u >> v;
  24.                 edges[i][0] = u;
  25.                 edges[i][1] = v;
  26.                 degree[u]++;
  27.                 degree[v]++;
  28.               }
  29.  
  30.               for(int i = 1 ; i <= Node ; ++i ){           //  cumulative sum of degree's of nodes and maintain it's copy in another array 
  31.                degree[i] += degree[i - 1];
  32.                copy_of_prefix[i] = degree[i];
  33.               }
  34.  
  35.               for(int i = 1 ; i <= Edge ; ++i){
  36.                    int u = edges[i][0];
  37.                    int v = edges[i][1];
  38.                  graph[copy_of_prefix[u - 1]++] = v;      // Place nodes u and v , to their position in graph array 
  39.                  graph[copy_of_prefix[v - 1]++] = u;
  40.               }
  41.  
  42.               int Size = 2 * Edge;                        // Size of graph array is 2 * total edges , because for each edge we used two position               
  43.  
  44.                 dfs(1);                                   // Function to initiate Dfs
  45.  
  46.    return 0;
  47. }
Success #stdin #stdout 0s 19536KB
comments (?)
stdin
copy 
5
4
1 2
1 3
2 4
2 5
stdout
copy 
1 2 4 5 3
https://ideone.com/Jb0M9T
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!