A83483.Connected Components?

普及/提高-

通过率:0%

时间限制:3.00s

内存限制:256MB

题目描述

给定一个包含 nn 个顶点和 (n2)\binom{n}{2} 条边的无向图。不同于直接给出图中存在的边,本题给出 mm 个无序对 (x,y)(x, y),表示在 xxyy 之间没有边连接。如果输入中没有出现的任意一对顶点之间都存在一条边。

你需要求出图中连通块的数量以及每个连通块的大小。连通块是指这样一个顶点集合 XX,满足集合中任何两点之间至少有一条路径相连,但如果将其他顶点加入集合 XX,就不再满足这个条件。

输入格式

第一行包含两个整数 nnmm1n2000001 \leq n \leq 2000000m5000000 \leq m \leq 500000)。

接下来 mm 行,每行包含两个整数 xxyy1x,yn1 \leq x, y \leq nxyx \neq y),表示在 xxyy 之间没有边连接。每对无序对最多出现一次;(x,y)(x, y)(y,x)(y, x) 视为相同的对(同一测试中不会重复出现)。如果某对顶点未在输入中出现,表示它们之间存在一条边。

输出格式

首先输出 kk,表示该图中连通块的数量。

然后输出 kk 个整数,表示每个连通块的大小。请按非递减顺序输出这些整数。

输入输出样例

  • 输入#1

    5 5
    1 2
    3 4
    3 2
    4 2
    2 5
    

    输出#1

    2
    1 4 
首页