主页 / user-652753

Николай Коптев's questions

Martin Hope
Николай Коптев
Asked: 2025-03-07 03:02:07 +0000 UTC
  • 5

当发送问题解决方案进行验证时，验证系统会通知您答案不正确。 任务正文：

给定一个无向图，可能存在环路和多条边。需要找到一个包含数字为 1 的顶点的连通分量。

输入格式

第一行包含两个整数N（1≤N≤10^3）和M（0≤M≤5×10^5）——表示图中顶点和边的数量。接下来的 M 行列出了边 - 定义连接边的顶点的数量的数字对。顶点从一开始编号。

输出格式

在第一行中，打印数字 K——连接组件中的顶点数。在第二行中，打印 K 个整数 - 连通分量的顶点，按数字升序排列。

内存限制：256 MB


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(" ")));
    }
}
java