fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. import java.util.function.*;
  4.  
  5. class Ideone
  6. {
  7.     public static void main(String[] args)
  8.     {
  9.         Graph g = Graph.read();
  10.  
  11.         g.dfs(0, r -> {
  12.             System.out.println("node: " + r.node + ", depth: " + r.depth);
  13.             return false;
  14.         });
  15.     }
  16. }
  17.  
  18. class Graph extends ArrayList<ArrayList<Integer>>
  19. {
  20.     public Graph(int size)
  21.     {
  22.         super(size);
  23.         for (int i = 0; i < size; i++)
  24.         {
  25.             add(new ArrayList<>());
  26.         }
  27.     }
  28.     static Graph read()
  29.     {
  30.         Scanner in = new Scanner(System.in);
  31.         int size = in.nextInt();
  32.         int edge = in.nextInt();
  33.         Graph g = new Graph(size);
  34.         for (int i = 0; i < edge; i++)
  35.         {
  36.             int a = in.nextInt();
  37.             int b = in.nextInt();
  38.             g.get(a).add(b);
  39.             g.get(b).add(a);
  40.         }
  41.         return g;
  42.     }
  43.  
  44.     class Reach
  45.     {
  46.         public int depth, node;
  47.         Reach(int d, int n) { depth = d; node = n; }
  48.     }
  49.  
  50.     Reach dfs(int start, Function<Reach, Boolean> callback)
  51.     {
  52.         boolean[] visited = new boolean[size()];
  53.         visited[start] = true;
  54.         ArrayDeque<Reach> stack = new ArrayDeque<>();
  55.         stack.addLast(new Reach(0, start));
  56.         while (!stack.isEmpty())
  57.         {
  58.             Reach r = stack.pollLast();
  59.             if (callback.apply(r))
  60.             {
  61.                 return r;
  62.             }
  63.             for (int t : get(r.node))
  64.             {
  65.                 if (visited[t])
  66.                 {
  67.                     continue;
  68.                 }
  69.                 visited[t] = true;
  70.                 stack.addLast(new Reach(r.depth + 1, t));
  71.             }
  72.         }
  73.         return null;
  74.     }
  75. }
  76.  
Success #stdin #stdout 0.12s 37836KB
comments (?)
stdin
copy 
7 6
0 1
0 2
1 3
1 4
2 5
4 6
stdout
copy 
node: 0, depth: 0
node: 2, depth: 1
node: 5, depth: 2
node: 1, depth: 1
node: 4, depth: 2
node: 6, depth: 3
node: 3, depth: 2
https://ideone.com/YvyXid
competitive programming
Graph DFS
language:
Java (HotSpot 12)
created:
4 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!