#316. Air Raid
Air Raid
题目描述
给定一个有向无环图,用尽量少的有向路径覆盖全部顶点。每个顶点恰好属于一条路径;单个顶点也可以作为一条路径。求最少路径条数。
输入格式
第一行测试组数。每组先输入 n、m,再输入 m 条有向边。
输出格式
每组输出最少路径条数。
样例输入
2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3
样例输出
2
1
题意整理;原题与输入输出格式对照。
给定一个有向无环图,用尽量少的有向路径覆盖全部顶点。每个顶点恰好属于一条路径;单个顶点也可以作为一条路径。求最少路径条数。
第一行测试组数。每组先输入 n、m,再输入 m 条有向边。
每组输出最少路径条数。
2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3
2
1
题意整理;原题与输入输出格式对照。