Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Graphs

DFS of a Graph

Easy · Graphs · Asked at Amazon, Microsoft, Google, Samsung

Print the depth-first search order starting from node 1. From each node, try its neighbours in increasing order and go as deep as possible before backtracking. Print only the nodes reachable from node 1.

Input

First line: n m. Next m lines: u v — an undirected edge (nodes are 1..n).

Output

The DFS order, space-separated.

Constraints

Recursive DFS with sorted adjacency lists. An iterative version must push neighbours in reverse order to visit the smallest first.

Example 1

Input

5 4
1 2
1 3
2 4
3 5

Output

1 2 4 3 5

Example 2

Input

4 3
1 4
1 2
4 3

Output

1 2 4 3

Hints

  1. Sort each adjacency list so the smallest neighbour is tried first.
  2. Recursive DFS: visit a node, then recurse into each unvisited neighbour in order.

Approach

Build sorted adjacency lists. dfs(u): mark u, output it, then for each neighbour in increasing order call dfs(v) if v is unvisited. This goes as deep as possible before backtracking. For very deep graphs, use an explicit stack (pushing neighbours in reverse order) or a larger stack size, as the Java solution does.

Complexity: O(n + m log m) time · O(n + m) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;
vector<bool> seen;
vector<int> order;

void dfs(int u) {
    seen[u] = true;
    order.push_back(u);
    for (int v : adj[u])
        if (!seen[v]) dfs(v);
}

int main() {
    int n, m;
    cin >> n >> m;
    adj.assign(n + 1, {});
    seen.assign(n + 1, false);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (auto &a : adj) sort(a.begin(), a.end());
    dfs(1);
    for (size_t i = 0; i < order.size(); i++) cout << order[i] << (i + 1 < order.size() ? " " : "\n");
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
adj = [[] for _ in range(n + 1)]
for i in range(m):
    u, v = data[2 + 2 * i], data[3 + 2 * i]
    adj[u].append(v)
    adj[v].append(u)
for a in adj:
    a.sort()
seen = [False] * (n + 1)
order, stack = [], [1]
# iterative DFS: push neighbours in reverse so the smallest is explored first
while stack:
    u = stack.pop()
    if seen[u]:
        continue
    seen[u] = True
    order.append(u)
    for v in reversed(adj[u]):
        if not seen[v]:
            stack.append(v)
print(*order)

Java solution

import java.util.*;
import java.io.*;

public class Main {
    static List<List<Integer>> adj = new ArrayList<>();
    static boolean[] seen;
    static StringBuilder sb = new StringBuilder();

    static void dfs(int u) {
        seen[u] = true;
        sb.append(sb.length() > 0 ? " " : "").append(u);
        for (int v : adj.get(u))
            if (!seen[v]) dfs(v);
    }

    public static void main(String[] args) throws Exception {
        Thread t = new Thread(null, () -> {
            try {
                StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
                in.nextToken();
                int n = (int) in.nval;
                in.nextToken();
                int m = (int) in.nval;
                for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
                for (int i = 0; i < m; i++) {
                    in.nextToken();
                    int u = (int) in.nval;
                    in.nextToken();
                    int v = (int) in.nval;
                    adj.get(u).add(v);
                    adj.get(v).add(u);
                }
                for (List<Integer> a : adj) Collections.sort(a);
                seen = new boolean[n + 1];
                dfs(1);
                System.out.println(sb);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }, "main", 1 << 26);
        t.start();
        t.join();
    }
}

Solve DFS of a Graph online · All practice problems