Поиск в глубину в графе. Yandex contest (Решено)

Question

Отправляя на проверку решение задачи, система проверки уведомляет о неправильном ответе. Текст задачи:

Дан неориентированный граф, возможно с петлями и кратными ребрами. Необходимо найти компоненту связности, содержащую вершину с номером 1.

Формат ввода

В первой строке записаны два целых числа N (1≤N≤10^3) и M (0≤M≤5×10^5) — количество вершин и ребер в графе. В последующих M строках перечислены ребра — пары чисел, определяющие номера вершин, которые соединяют ребра. Вершины нумеруются с единицы.

Формат вывода

В первой строке выведите число K — количество вершин в компоненте связности. Во второй строке выведите K целых чисел — вершины компоненты связности, перечисленные в порядке возрастания номеров.

Ограничение памяти: 256 МБ


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class GraphTraversal {

    public static void main(String[] args) {
        try(BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            int[] graphMetaData = Arrays.stream(reader.readLine().split("\\s")).mapToInt(Integer::valueOf).toArray();
            int n = graphMetaData[0];
            int m = graphMetaData[1];
            int start = 1;
            if(m > 0) {
                Set<Integer> visited = new HashSet<>();
                Map<Integer, Set<Integer>> graph = new HashMap<>(n);
                for(int i = 0; i < m; i++) {
                    int[] nodeData = Arrays.stream(reader.readLine().split("\\s")).mapToInt(Integer::valueOf).toArray();
                    int node1 = nodeData[0];
                    int node2 = nodeData[1];
                    addNodesInGraph(graph, node1, node2);
                }
                travel(graph, start, visited);
                print(visited);
            } else {
                System.out.println(1);
                System.out.println(1);
            }
        } catch(IOException e) {
            e.printStackTrace();
        }
    }
    
    private static void addNodesInGraph(Map<Integer, Set<Integer>> graph, int node1, int node2) {
        graph.computeIfAbsent(node1, k -> new HashSet<Integer>()).add(node2);
        graph.computeIfAbsent(node2, k -> new HashSet<Integer>()).add(node1);
    }
    
//  Alternative way by recursion
    private static void travel(Map<Integer, Set<Integer>> graph, int node, Set<Integer> visited) {
        visited.add(node);
        for(int neighbour : graph.getOrDefault(node, Collections.emptySet())) {
            if(!visited.contains(neighbour)) {
                travel(graph, neighbour, visited);
            }
        }
    }
    
//  Alternative way by queue
//  private static void travel(Map<Integer, Set<Integer>> graph, int start, Set<Integer> visited) {
//      Queue<Integer> noVisited = new LinkedList<>();
//      noVisited.add(start);
//      while(noVisited.size() > 0) {
//          int node = noVisited.remove();
//          if(!visited.contains(node)) {               
//              Set<Integer> neighbours = graph.getOrDefault(node, Collections.emptySet());
//              noVisited.addAll(neighbours);
//              visited.add(node);
//          }
//      }
//  }
    
    private static void print(Set<Integer> visited) {
        List<Integer> result = new ArrayList<>(visited);
        result.sort(Comparator.naturalOrder());
        System.out.println(visited.size());
        System.out.println(result.stream().map(String::valueOf).collect(Collectors.joining(" ")));
    }
}

Answer 1

Решение найдено. Проблема была в методе travel(). Вместо graph.get(node) следует использовать graph.getOrDefault(node, Collections.emptySet()). Т.к. при определенных входных данных можно получить NullPointerException.

Answer 2

Честно говоря, с трудом пролез по вводу. Обычный Scanner не успевает:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    public static void main(String... args) throws IOException {
        try (
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            String[] words = reader.readLine().split(" ");
            int n = Integer.parseInt(words[0]);
            int m = Integer.parseInt(words[1]);

            List<Set<Integer>> graph = new ArrayList<Set<Integer>>(n);
            for (int i = 0; i < n; ++i) {
                graph.add(new HashSet<Integer>());
            }
            
            for (int j = 0; j < m; ++j) {
                words = reader.readLine().split(" ");
                int i1 = Integer.parseInt(words[0]) - 1;
                int i2 = Integer.parseInt(words[1]) - 1;
                graph.get(i1).add(i2);
                graph.get(i2).add(i1);
            }

            boolean[] visited = new boolean[n];
            dfs(graph, 0, visited);

            int c = 0;
            for (boolean v : visited) {
                if (v) {
                    ++c;
                }
            }
            writer.write(Integer.toString(c));
            writer.write('\n');

            boolean first = true;
            for (int i = 0; i < n; ++i) {
                if (visited[i]) {
                    if (first) {
                        first = false;
                    } else {
                        writer.write(' ');
                    }
                    writer.write(Integer.toString(i + 1));
                }
            }
            writer.write('\n');
        }
    }

    private static void dfs(List<Set<Integer>> graph, int i, boolean[] visited) {
        if (!visited[i]) {
            visited[i] = true;
            for (int j : graph.get(i)) {
                dfs(graph, j, visited);
            }
        }
    }
}

БЛОГ НА HUSL

Поиск в глубину в графе. Yandex contest (Решено)

Ответы (2 шт):