#P10366. [2021年联测]强连通图
[2021年联测]强连通图
题目描述
给定一张有向图。请加入尽可能少的有向边,使图中任意两个顶点都可以互相到达。添加后不能有重边或自环。若有多组最优方案,输出任意一组。
输入格式
第一行两个整数 ,表示顶点数和边数。接下来 行,每行两个整数 ,表示从 到 的一条有向边。初始图没有重边或自环。
输出格式
第一行一个整数 ,表示最少需要添加的边数。接下来 行,每行两个整数 ,表示一条新加入的有向边。
样例 1
3 3
1 2
2 3
1 3
1
3 1
样例 2
1 0
0
样例 3
2 2
1 2
2 1
0
样例 4
6 5
1 4
2 4
3 5
4 6
5 6
3
6 1
6 2
6 3
数据范围
,,。
| 原子任务 | 分值 | 上界 |
|---|---|---|
| 1 | 10 | 15 |
| 2 | 1000 | |
| 3 | 20 | 5000 |
| 4 | 50000 | |
| 5 | 40 |