CSES1699 航班路线请求
#CS1699. 航班路线请求
航班路线请求
题目背景
翻译自 CSES-1699 题。
题目描述
有 n 个城市，每个城市都有一个机场，但目前没有航班连接。你将获得 m 个请求，要求在这些城市之间建立航线。
你的任务是确定最少需要多少个单向航班连接，才能满足所有的请求。
输入格式
第一行包含两个整数 n 和 m，分别表示城市的数量和请求的数量。城市编号为 1,2,…,n1, 2, \dots, n1,2,…,n。
接下来的 m 行，每行包含两个整数 a 和 b，表示必须存在一条从城市 a 到城市 b 的航线。每个请求都是唯一的。
输出格式
输出一个整数，表示满足所有请求所需的最少航班连接数。
样例
4 5
1 2
2 3
2 4
3 1
3 4
4
样例1解释 你可以建立如下的航班连接：
-
1→21 \to 21→2
-
2→32 \to 32→3
-
2→42 \to 42→4
-
3→13 \to 13→1
这样就可以满足从城市 3 到城市 4 的要求，路径是：3→1→2→43 \to 1 \to 2 \to 43→1→2→4。
说明/提示