6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 0 0
45
Shrek is a postman working in the mountain, whose routine work is sending mail to n villages. Unfortunately, road between villages is out of repair for long time, such that some road is one-way road. There are even some villages that can’t be reached from any other village. In such a case, we only hope as many villages can receive mails as possible.
Shrek hopes to choose a village A as starting point (He will be air-dropped to this location), then pass by as many villages as possible. Finally, Shrek will arrived at village B. In the travelling process, each villages is only passed by once. You should help Shrek to design the travel route.
There are 2 integers, n and m, in first line. Stand for number of village and number of road respectively.
In the following m line, m road is given by identity of villages on two terminals. From v1 to v2. The identity of village is in range [1, n].
Output maximum number of villages Shrek can pass by.
Input
4 3
1 4
2 4
4 3
Output
3
1 <= n <= 1,000,000
0 <= m <= 1,000,000
These is no loop road in the input.
Time: 2 sec
Memory: 256 MB
Topological sorting
Shrek是一个大山里的邮递员，每天负责给所在地区的n个村庄派发信件。但杯具的是，由于道路狭窄，年久失修，村庄间的道路都只能单向通过，甚至有些村庄无法从任意一个村庄到达。这样我们只能希望尽可能多的村庄可以收到投递的信件。
Shrek希望知道如何选定一个村庄A作为起点（我们将他空投到该村庄），依次经过尽可能多的村庄，路途中的每个村庄都经过仅一次，最终到达终点村庄B，完成整个送信过程。这个任务交给你来完成。
第一行包括两个整数n，m，分别表示村庄的个数以及可以通行的道路的数目。
以下共m行，每行用两个整数v1和v2表示一条道路，两个整数分别为道路连接的村庄号，道路的方向为从v1至v2，n个村庄编号为[1, n]。
输出一个数字，表示符合条件的最长道路经过的村庄数。
见英文题面
1 ≤ n ≤ 1,000,000
0 ≤ m ≤ 1,000,000
输入保证道路之间没有形成环
时间：2 sec
空间：256 MB
拓扑排序
In general, given the preorder traversal sequence and postorder traversal sequence of a binary tree, we cannot determine the binary tree.
Figure 1
In Figure 1 for example, although they are two different binary tree, their preorder traversal sequence and postorder traversal sequence are both of the same.
But for one proper binary tree, in which each internal node has two sons, we can uniquely determine it through its given preorder traversal sequence and postorder traversal sequence.
Label n nodes in one binary tree using the integers in [1, n], we would like to output the inorder traversal sequence of a binary tree through its preorder and postorder traversal sequence.
The 1st line is an integer n, i.e., the number of nodes in one given binary tree,
The 2nd and 3rd lines are the given preorder and postorder traversal sequence respectively.
The inorder traversal sequence of the given binary tree in one line.
Input
5
1 2 4 5 3
4 5 2 3 1
Output
4 2 5 1 3
For 95% of the estimation, 1 <= n <= 1,000,00
For 100% of the estimation, 1 <= n <= 4,000,000
The input sequence is a permutation of {1,2…n}, corresponding to a legal binary tree.
Time: 2 sec
Memory: 256 MB
Figure 2
In Figure 2, observe the positions of the left and right children in preorder and postorder traversal sequence.
一般来说，给定二叉树的先序遍历序列和后序遍历序列，并不能确定唯一确定该二叉树。
（图一）
比如图一中的两棵二叉树，虽然它们是不同二叉树，但是它们的先序、后序遍历序列都是相同的。
但是对于“真二叉树”（每个内部节点都有两个孩子的二叉树），给定它的先序、后序遍历序列足以完全确定它的结构。
将二叉树的n个节点用[1, n]内的整数进行编号，输入一棵真二叉树的先序、后序遍历序列，请输出它的中序遍历序列。
第一行为一个整数n，即二叉树中节点的个数。
第二、三行为已知的先序、后序遍历序列。
仅一行，给定真二叉树的中序遍历序列。
见英文题面
对于95%的测例：1 ≤ n ≤ 1,000,000
对于100%的测例：1 ≤ n ≤ 4,000,000
输入的序列是{1,2…n}的排列，且对应于一棵合法的真二叉树
时间：2 sec
空间：256 MB
观察左、右孩子在先序、后序遍历序列中的位置
重温视频05e5-3
目测一辈子也忘不了二叉树重构怎么写了…………
继续阅读
Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in “zigzagging order” — that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15.
Each input file contains one test case. For each case, the first line gives a positive integer N (<= 30), the total number of nodes in the binary tree. The second line gives the inorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the zigzagging sequence of the tree in a line. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:
8 12 11 20 17 1 15 8 5 12 20 17 11 15 8 5 1
Sample Output:
1 11 5 8 17 12 20 15