#P10366. [2021年联测]强连通图

    ID: 9484 传统题 1000ms 512MiB 尝试: 10 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-Tarjan 强连通分量算法缩点深度优先搜索图构造

[2021年联测]强连通图

题目描述

给定一张有向图。请加入尽可能少的有向边,使图中任意两个顶点都可以互相到达。添加后不能有重边或自环。若有多组最优方案,输出任意一组。

输入格式

第一行两个整数 n,mn,m,表示顶点数和边数。接下来 mm 行,每行两个整数 u,vu,v,表示从 uu 到 vv 的一条有向边。初始图没有重边或自环。

输出格式

第一行一个整数 kk,表示最少需要添加的边数。接下来 kk 行,每行两个整数 u,vu,v,表示一条新加入的有向边。

样例 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≤n≤1061\le n\le10^6,0≤m≤min⁡(106,n(n−1))0\le m\le\min(10^6,n(n-1)),1≤u,v≤n1\le u,v\le n。

原子任务 分值 nn 上界
1 10 15
2 1000
3 20 5000
4 50000
5 40 10610^6

原 PDF 题面