#P18384. DFS Order 6
DFS Order 6
DFS Order 6
题目描述
给定一个有 个顶点的连通无向简单图 ,顶点编号为 ,以及起点 。按照下面的规则进行深度优先搜索:
DFS(x):
标记 x 已访问
将 x 加入访问顺序
按顶点编号从小到大枚举 x 的所有相邻顶点 y:
若 y 尚未访问:
DFS(y)
Generate(G, s):
将所有顶点标记为尚未访问
清空访问顺序
DFS(s)
返回访问顺序
每个顶点只在第一次访问时加入顺序。由于总是按编号升序枚举邻居,固定图和起点后,这个 DFS 顺序唯一确定。

上图有 个顶点和 条边。从顶点 出发的 DFS 顺序为 。
现在给出 个排列 。其中 声称是从顶点 出发得到的 DFS 顺序。
请构造任意一个顶点为 的连通无向简单图,使从每个顶点 出发的 DFS 顺序都恰好为 ;或者判断不存在这样的图。
简单图不允许自环和重边。
输入格式
输入包含多组测试数据。第一行包含整数 ()。
对于每组测试数据:
第一行包含一个整数 ()。
接下来 行,第 行包含 个整数 。保证这一行是 的一个排列,并且 。
保证所有测试数据的 之和不超过 。
输出格式
对每组测试数据:
如果不存在满足要求的图,输出一行 No。
否则第一行输出 Yes,第二行输出边数 ,其中
接下来 行,每行输出两个整数 (,),表示图中的一条无向边。
输出的图必须简单、连通,并且从每个起点得到的 DFS 顺序都与输入一致。可以输出任意一种符合要求的图,边的输出顺序及每条边两个端点的输出顺序均不限。
当 时,合法图的边数为 。
样例输入
2
3
1 2 3
2 1 3
3 2 1
3
1 2 3
2 3 1
3 1 2
样例输出
Yes
2
1 2
2 3
No
样例说明
第一组数据中,路径 是一种合法构造。从三个起点分别得到 、、。
第二组数据中,不存在符合要求的图。