#CF920E. Connected Components?
Connected Components?
好的,这是您要求的算法题题面的中文翻译和排版:
E. 连通分量?
每个测试点的时间限制: 秒
每个测试点的内存限制: MB
输入:标准输入
输出:标准输出
给定一个包含 个顶点和若干条边的无向图。与通常直接给出图中存在的边不同,本题会给出 个无序对 ,表示顶点 和 之间没有边。如果某对顶点没有在输入中列出,则这两个顶点之间存在一条边。
你需要找出该图中的连通分量个数,以及每个连通分量的大小。一个连通分量是指顶点集合 ,满足对于该集合中的任意两个顶点,图中至少存在一条路径连接它们,但如果将任何其他顶点加入 ,这一性质就会被破坏。
输入
第一行包含两个整数 和 (,)。
接下来 行,每行包含两个整数 和 (,),表示顶点 和 之间没有边。每对顶点最多出现一次; 和 被视为相同(因此它们不会在同一个测试用例中同时出现)。如果某对顶点没有在输入中列出,则这两个顶点之间存在一条边。
输出
首先输出一个整数 —— 图中连通分量的个数。
然后输出 个整数 —— 每个连通分量的大小。这些整数应按非递减顺序输出。
输入示例
5 5
1 2
3 4
3 2
4 2
2 5
输出示例
2
1 4