7762: Tarjan 算法求 dfn 和 low 数组
[Creator : ]
Description
提供一个有向图。该图有 $n$ 个顶点，顶点编号为 $1 \sim n$，有 $m$ 条有向边。
求按照顶点次数输出 Tarjan 算法对应的 dfn 数组和 low 数组数据。
请注意，使用不同方式存储图，对应的 dfn 和 low 数组数据不同。
这里我们使用数组来存储。具体代码如下：
本题只是为了让初学者掌握 dfn 和 low 罢了，没有特别要求顶点从小到大，因为数组保存邻接表不支持排序。
求按照顶点次数输出 Tarjan 算法对应的 dfn 数组和 low 数组数据。
请注意，使用不同方式存储图，对应的 dfn 和 low 数组数据不同。
这里我们使用数组来存储。具体代码如下：
void add(LL a, LL b) {
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
如果您使用 vector 来保存。请务必如下插入边。
auto it = adj[a].begin(); adj[a].insert(it, b);
本题只是为了让初学者掌握 dfn 和 low 罢了，没有特别要求顶点从小到大，因为数组保存邻接表不支持排序。
Input
第一行包括两个整数 $n,m$，表示有 $n$ 个顶点，$m$ 条边。
第二行到第 $m+1$ 行，每行包括两个整数 $a,b$，表示顶点 $a$ 到顶点 $b$ 之间存在一条有向边。
第二行到第 $m+1$ 行，每行包括两个整数 $a,b$，表示顶点 $a$ 到顶点 $b$ 之间存在一条有向边。
Output
一共包括 $2$ 行。
第一行包括 $n$ 个整数，第 $i$ 个整数表示 dfn[i] 的数据。
第二行包括 $n$ 个整数，第 $i$ 个整数表示 low[i] 的数据。
第一行包括 $n$ 个整数，第 $i$ 个整数表示 dfn[i] 的数据。
第二行包括 $n$ 个整数，第 $i$ 个整数表示 low[i] 的数据。
Constraints
$1 \leq n \leq 5\times 10^5$
$0 \leq m \leq \frac{n*(n-1)}{2}$
$0 \leq m \leq \frac{n*(n-1)}{2}$
Sample 1 Input
6 7
1 2
2 4
4 1
1 3
3 4
3 5
5 6
Sample 1 Output
1 6 2 5 3 4
1 5 1 1 3 4
Sample 2 Input
7 12
1 2
1 3
2 4
3 2
3 4
3 5
3 6
5 4
5 6
6 1
7 3
7 5
Sample 2 Output
1 6 2 5 4 3 7
1 5 1 5 3 1 2
Sample 3 Input
4 5
1 2
2 1
2 3
3 4
4 3
Sample 3 Output
1 2 3 4
1 1 3 3