OI题库

【题目描述】

排序网络是这样一个模型:

有n条水平的导线，由上至下分别标号为1至n，导线与导线之间不相交。在任意两导线之间可以搭上“电桥”。每条导线的左端放置一数字，数字沿导线由左向右同步运行，当遇上一电桥时，比较电桥两端的两根导线上的数字，将其中较大的放到上面的导线上，而将较小的放到下面的导线上，然后继续运行，保证同一时刻最多只有一个电桥。（如图）

若一个n行的排序网络共包含m个电桥，对于左端输入的任意顺序的数列，都能在右端得到一个由大到小的数列，我们称这个排序网络是一个完全排序网络。

我们的程序需要做的，就是判断一个排序网络是否是一个完全排序网络。

【输入格式】

第一行是一个整数N，表示排序网络的行数

第二行是一个整数M，表示排序网络的电桥数

接下来的M行，每行有两个整数i,j，表示导线i和j之间有一条电桥。

电桥按从左向右的顺序依次给出。

【输出格式】

一行。若这个排序网络是完全排序网络，那么输出"Yes!"，否则输出"No!"。

当然，你的输出中不包含引号

【样例输入】

6
15
1 2
2 3
3 4
4 5
5 6
1 2
2 3
3 4
4 5
1 2
2 3
3 4
1 2
2 3
1 2

【样例输出】

Yes!

【提示】

样例描述了一个等价于N=6的冒泡排序法的排序网络
对于40%的数据，N<=10,M<=100
对于100%的数据，N<=100,M<=200000

【来源】

NOI1999北京集训队训练题
杨江明，《论数学策略在信息学问题中的应用》，IOI2000国家集训队论文集