codeforces 920E(非原创)
2 seconds
256 megabytes
standard input
standard output
You are given an undirected graph consisting of n vertices and edges. Instead of giving you the edges that exist in the graph, we give you m unordered pairs (x, y) such that there is no edge between x and y, and if some pair of vertices is not listed in the input, then there is an edge between these vertices.
You have to find the number of connected components in the graph and the size of each component. A connected component is a set of vertices X such that for every two vertices from this set there exists at least one path in the graph connecting these vertices, but adding any other vertex to X violates this rule.
The first line contains two integers n and m (1 ≤ n ≤ 200000, ).
Then m lines follow, each containing a pair of integers x and y (1 ≤ x, y ≤ n, x ≠ y) denoting that there is no edge between x and y. Each pair is listed at most once; (x, y) and (y, x) are considered the same (so they are never listed in the same test). If some pair of vertices is not listed in the input, then there exists an edge between those vertices.
Firstly print k — the number of connected components in this graph.
Then print k integers — the sizes of components. You should output these integers in non-descending order.
5 5
1 2
3 4
3 2
4 2
2 5
2
1 4
这题是求补图的联通块个数。用到了链表加bfs的强优化。
本人学习博客:http://blog.csdn.net/just_sort/article/details/54862268
最新文章
- ORACLE NUMBER类型Scale为0引发的问题
- 获取 view所在的VC
- mysql定时器Events
- iOS8中使用CoreLocation定位[转]
- window.onresize 多次触发的解决方法
- bzoj 1503: [NOI2004]郁闷的出纳员 Treap
- listview——显示窗体
- Storm源码分析--Nimbus-data
- ubuntu通过虚拟域名访问不了 502 / 网络错误
- 浏览器怎么解析一个hmtl文档
- 【日常学习】【线性DP】codevs1044 拦截导弹题解
- GIT工程迁移方法总结
- zeppelin中连接hive和impala
- Docker安装nexus
- 安装mysql8.0.12以及修改密码和Navicat的连接
- 洛谷P3376 【模板】网络最大流
- Jvm中时区设置方式
- Qt error ------ no matching function for call to QObject::connect(QSpinBox*&;, <;unresolved overloaded function type>;, QSlider*&;, void (QAbstractSlider::*)(int))
- 枚举Enum转换为List,获取枚举的描述
- JUnit4 测试示例