Java纠错/优化求助 能过样例,一个WA,四个MLE
查看原帖
Java纠错/优化求助 能过样例,一个WA,四个MLE
254291
lml_Photon楼主2024/10/19 12:35

用的邻接表,也排了序,但是第一个测试点WA。

Java有什么比较好的写图的方式吗?

代码如下,感谢

import java.util.*;

public class P5318 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        Graph graph = new Graph(n);

        for (int i = 0; i < m; i++) {
            graph.addEdge(sc.nextInt()-1, sc.nextInt()-1);
        }

        graph.sort();
        graph.dfs();
        System.out.println();
        graph.bfs();
    }

    static class Graph {
        HashMap<Integer, List<Integer>> map;
        Boolean[] visited;

        Graph(int n) {
            map = new HashMap<>();
            visited = new Boolean[n];
        }

        void addEdge(int src, int dest) {
            map.computeIfAbsent(src, _ -> new ArrayList<>()).add(dest);
        }

        void sort(){
            for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
                Collections.sort(entry.getValue());
            }
        }

        void bfs(){
            Queue<Integer> queue = new LinkedList<>();
            Arrays.fill(visited, false);

            queue.add(0);
            visited[0] = true;
            while(!queue.isEmpty()){
                int cur = queue.poll();
                System.out.print( cur+1 + " " );
                if (map.get(cur) != null){
                    for (int i: map.get(cur)) {
                        if (!visited[i]) {
                            queue.add(i);
                            visited[i] = true;
                        }
                    }
                }
            }
        }

        void dfs(){
            Stack<Integer> stack = new Stack<>();
            Arrays.fill(visited, false);

            stack.push(0);
            visited[0] = true;
            while(!stack.isEmpty()){
                int cur = stack.pop();
                System.out.print( cur+1 + " " );
                List<Integer> list = map.get(cur);
                if (list != null){
                    for (int i = list.size() - 1; i >= 0; i--) {
                        int node = list.get(i);
                        if (!visited[node]) {
                            stack.push(node);
                            visited[node] = true;
                        }
                    }
                }
            }
        }
    }
}
2024/10/19 12:35
加载中...