用的邻接表,也排了序,但是第一个测试点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;
}
}
}
}
}
}
}