【深基18.例3】查找文献
题目描述
小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个(也有可能没有)参考文献的链接指向别的博客文章。小 K 求知欲旺盛,如果他看了某篇文章,那么他一定会去看这篇文章的参考文献(如果他之前已经看过这篇参考文献的话就不用再看它了)。
假设洛谷博客里面一共有 $n(n\le10^5)$ 篇文章(编号为 1 到 $n$)以及 $m(m\le10^6)$ 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章,请帮助小 K 设计一种方法,使小 K 可以不重复、不遗漏的看完所有他能看到的文章。
这边是已经整理好的参考文献关系图,其中,文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。

请对这个图分别进行 DFS 和 BFS,并输出遍历结果。如果有很多篇文章可以参阅,请先看编号较小的那篇(因此你可能需要先排序)。
输入格式
共 $m+1$ 行,第 1 行为 2 个数,$n$ 和 $m$,分别表示一共有 $n(n\le10^5)$ 篇文章(编号为 1 到 $n$)以及$m(m\le10^6)$ 条参考文献引用关系。
接下来 $m$ 行,每行有两个整数 $X,Y$ 表示文章 X 有参考文献 Y。
输出格式
共 2 行。
第一行为 DFS 遍历结果,第二行为 BFS 遍历结果。
样例 #1
样例输入 #1
1 2 3 4 5 6 7 8 9 10
| 8 9 1 2 1 3 1 4 2 5 2 6 3 7 4 7 4 8 7 8
|
样例输出 #1
1 2
| 1 2 5 6 3 7 8 4 1 2 3 4 5 6 7 8
|
分析
这篇文章主要还是因为Java在洛谷 栈深度过高,会出现报错,所以需要用一个new Thread 来提高stackSize。
题解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
| import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.*;
public class P5318 { static int n; static int m; static List<Integer>[] node; static boolean[] vis;
public static void main(String[] args) { new Thread(null, () -> { try {
n = nextInt(); m = nextInt(); node = new ArrayList[n + 1]; for (int i = 1; i <= n; i++) node[i] = new ArrayList<>();
for (int i = 0; i < m; i++) { int x = nextInt(); int y = nextInt(); node[x].add(y); }
for (int i = 1; i <= n; i++) Collections.sort(node[i]);
vis = new boolean[n + 1]; dfs(1);
System.out.println(); Arrays.fill(vis, false);
Queue<Integer> queue = new ArrayDeque<>(); queue.offer(1); vis[1] = true; while (!queue.isEmpty()) { int x = queue.poll(); System.out.print(x + " "); for (int y : node[x]) { if (!vis[y]) { queue.offer(y); vis[y] = true; } } }
} catch (Exception e) { } }, "114514", 1 << 24).start(); } static void dfs(int x) { if (vis[x]) return;
vis[x] = true; System.out.print(x + " "); for (int v : node[x]) { dfs(v); } }
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int nextInt() throws IOException { st.nextToken(); return (int) st.nval; }
}
|