无向图的连通分量
测试数据来自 yunhua/1623
作业已超过截止时间,您无法递交本题目。
时间限制:1秒 内存限制:256M
【问题描述】
给出 \(N\)(编号为 \(1\sim N\))个顶点,\(M\) 条边的无向图,请计算并输出该图的连通分量数。
【输入格式】
第一行包含两个整数:\(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
【数据说明】
对于 \(100\%\) 的数据 \(1≤N≤100000\),\(1≤M≤500000\)。
【来源】
Mr.he