P7033: 结交朋友
传统题
3.000s
时间限制
1024MB
内存限制
1 提交
1 解决
【题目描述】
【题目描述】
FJ
的 N（2≤N≤2×10
^5
）头编号为1…N 的奶牛之中初始时有 M（1≤M≤2×10
^5
）对朋友。奶牛们一头一头地离开农场去度假。第 i
天，第 i 头奶牛离开了农场，同时第 i 头奶牛的所有仍在农场的朋友互相都成为了朋友。问总共建立了多少新的朋友关系？
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 N
和 M。
以下 M
行每行包含两个整数 ui 和 vi，表示奶牛 ui
和 vi 是朋友（1≤ui,vi≤N，ui≠vi
）。每个奶牛无序对至多出现一次。
【
输出格式】
（输出至终端 /
标准输出）：
输出一行，包含形成的新的朋友关系的总数。不要计入初始时已经是朋友的奶牛对。
【
输入样例】
：
7 6
1 3
1 4
7 1
2 3
2 4
3 5
【
输出样例】
：
5
【样例说明】
第 1
天，三个新的朋友关系被建立：(3,4)，(3,7)
和 (4,7)。
第 3
天，两个新的朋友关系被建立：(4,5) 和 (5,7)。
【
测试点性质】
：
测试点 2-3
满足 N≤500。
测试点 4-7
满足 N≤10^4
。
测试点 8-17
没有额外限制。