问题2168--空袭2168: 空袭
时间限制: 1 Sec 内存限制: 128 MB
提交: 0 解决: 0
[提交] [状态] [讨论版] [命题人:]题目描述
考虑一个城镇，所有街道都是单向的，每条街道都从一个十字路口通向另一个十字路口。众所周知，从十字路口开始，穿过城镇的街道，你永远无法到达同一个十字路口，即城镇的街道没有形成自行车。
有了这些假设，你的任务就是编写一个程序，找到可以降落在城镇上的最少数量的伞兵，并以一种多于一名伞兵不访问十字路口的方式访问该镇的所有十字路口。每个伞兵降落在一个十字路口，并可以沿着城镇街道访问其他十字路口。每个伞兵的起始交叉路口没有限制。
输入
您的程序应读取数据集。输入文件的第一行包含数据集的编号。每个数据集都指定了城镇的结构，格式为：
no_of_intersections
no_of_streets
S1 E1
S2 E2
......
Sno_of_streets Eno_of_streets 每个数据集的第一行包含一个正整数no_of_intersections（大于 0 且小于或等于 120），这是城镇中的交叉点数。第二行包含一个正整数no_of_streets，即城镇中的街道数。接下来的no_of_streets线（城镇中每条街道一条）是随机排序的，表示城镇的街道。与街道 k （k <= no_of_streets） 对应的线由两个正整数组成，以一个空格分隔：Sk （1 <= Sk <= no_of_intersections） - 作为街道起点的交叉点的编号，以及 Ek （1 <= Ek < = no_of_intersections） - 作为街道终点的交叉点的编号。交集由从 1 到 no_of_intersections 的整数表示。
连续的数据集之间没有空行。输入数据正确。
输出
程序的结果在标准输出上。对于每个输入数据集，程序打印在一条线上，从线路的开头开始，一个整数：访问城镇所有十字路口所需的最小伞兵数量。
样例输入
2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3
样例输出
2
1
来源/分类
[提交] [状态]