A83483.Connected Components?
普及/提高-
通过率:0%
时间限制:3.00s
内存限制:256MB
题目描述
给定一个包含 n 个顶点和 (2n) 条边的无向图。不同于直接给出图中存在的边,本题给出 m 个无序对 (x,y),表示在 x 和 y 之间没有边连接。如果输入中没有出现的任意一对顶点之间都存在一条边。
你需要求出图中连通块的数量以及每个连通块的大小。连通块是指这样一个顶点集合 X,满足集合中任何两点之间至少有一条路径相连,但如果将其他顶点加入集合 X,就不再满足这个条件。
输入格式
第一行包含两个整数 n 和 m(1≤n≤200000,0≤m≤500000)。
接下来 m 行,每行包含两个整数 x 和 y(1≤x,y≤n,x=y),表示在 x 和 y 之间没有边连接。每对无序对最多出现一次;(x,y) 和 (y,x) 视为相同的对(同一测试中不会重复出现)。如果某对顶点未在输入中出现,表示它们之间存在一条边。
输出格式
首先输出 k,表示该图中连通块的数量。
然后输出 k 个整数,表示每个连通块的大小。请按非递减顺序输出这些整数。
输入输出样例
输入#1
5 5 1 2 3 4 3 2 4 2 2 5
输出#1
2 1 4