C. 最多边数

    传统题 1000ms 256MiB

最多边数

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

题目描述

一张有向图含有 NN 个点,MM 条边。点的编号为 11 ~ NN。没有重边,也没有自环。

现在你希望再添加一些边。添加边的规则是:

若图中存在有向边 <a,b> 和 <a,c>,则你可以添加边 <b,c> 和 <c,b>。如果要添加的边已经存在,则无需添加。

你可以不断在新图中按以上规则进行加边。

问:最终图中最多包含多少条边?

输入格式

第一行:两个整数 NN 和 MM

接下来 MM 行,每行两个整数 Xi,YiX_i, Y_i,表示从点 XiX_i 向点 YiY_i 有一条有向边。

输出格式

一个整数,表示最终图中包含的最多边数。

样例输入

5 4
1 2
1 3
4 3
4 5

样例输出

10

数据范围

100% 的数据满足:

  • 1≤N≤100 0001 ≤ N ≤ 100\,000
  • 0≤M≤200 0000 ≤ M ≤ 200\,000
  • 1≤Xi,Yi≤N1 ≤ X_i, Y_i ≤ N(1≤i≤M1 ≤ i ≤ M)
  • Xi≠YiX_i ≠ Y_i(1≤i≤M1 ≤ i ≤ M)
  • (Xi,Yi)≠(Xj,Xj)(X_i, Y_i) \ne (X_j, X_j)(1≤i<j≤M1 ≤ i < j ≤ M)

子任务

子任务 1 [5 分]

  • 满足 N≤100N ≤ 100。

子任务 2 [30 分]

  • 满足 N≤5000N ≤ 5000。

子任务 3 [65 分]

  • 满足 N≤100 000N ≤ 100\,000

2026-10-17

未参加
状态
已结束
规则
OI
题目
4
开始于
2026-10-17 7:30
结束于
2026-10-17 11:00
持续时间
3.5 小时
主持人
参赛人数
23