#P3355. [Usaco2004 Jan]有序奶牛

    ID: 2544 传统题 1000ms 128MiB 尝试: 61 已通过: 30 难度: 6 上传者: 标签>难度分类提高图论拓扑排序动态规划DAG 动态规划传递闭包位运算位集加速可达性贪心排序贪心CF2000bitset

[Usaco2004 Jan]有序奶牛

[USACO 2004 Jan] 有序奶牛

题目描述

约翰的 NN 头奶牛排成一行挤奶,编号 11 到 NN。约翰掌握 LL 条形如“奶牛 AA 在奶牛 BB 前面”的信息。这些信息没有矛盾,最后一条可以由其他信息推出。

约翰想删除尽可能多的信息,使原来的每条信息都仍可从保留的信息推出。例如,若已知 AA 在 BB 前、BB 在 CC 前,则可推出 AA 在 CC 前。求应该保留哪些信息。答案唯一。

输入格式

从标准输入读入。第一行是两个整数 N,LN,L。接下来 LL 行,每行两个整数 X,YX,Y,表示奶牛 XX 在奶牛 YY 前。信息互不重复。

输出格式

向标准输出输出。第一行是一个整数 UU,表示保留的信息数。接下来 UU 行,每行输出一条保留的信息 X,YX,Y。先按 XX 从小到大排列;若 XX 相同,再按 YY 从小到大排列。

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

提示

样例中,33 在 11 前、44 在 11 前都可以从保留的信息推出。四条保留的信息都不能由其余保留信息推出。

数据范围与约定

1≤N≤15001\le N\le 1500,1≤X,Y≤N1\le X,Y\le N。