/ Vijos / 题库 /

无向图的连通分量

无向图的连通分量

时间限制:1秒  内存限制:256M


【问题描述】

  给出 \(N\)(编号为 \(1\sim N\))个顶点,\(M\) 条边的无向图,请完成下列任务:

  任务1、计算并输出该图的连通分量数。

  任务2、计算并输出该图的最大连通分量。

【输入格式】

  第一行包含两个整数:\(N,M\)。
  接下来的 \(M\) 行,每行包含两个整数:\(x,y\),表示顶点 \(x\) 和顶点 \(y\) 有一条边。

【输出格式】

  第一行一个整数,表示图的连通分量个数。
  第二行一个整数,表示图的极大连通分量包含的顶点数

【输入输出样例】

 Input

8 8
1 2
1 3
2 3
4 5
6 5
5 8
7 8
4 7

 Output

2
5

【数据说明】

  对于 \(100\%\) 的数据 \(1≤N≤100000\),\(1≤M≤500000\)。

【来源】

  Mr.he

信息

ID
1603
难度
9
分类
图结构 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
被复制
5
上传者