当发送问题解决方案进行验证时,验证系统会通知您答案不正确。 任务正文:
给定一个无向图,可能存在环路和多条边。需要找到一个包含数字为 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(" ")));
}
}