链表

办公楼biu

 2020.09.04 20:13  2023.09.01 18:14  ACM  链表  图论 󰈭 947字

给出一张图，求出其补图所有联通块的个数及其大小。黑暗爆炸OJ 1098 容易想到$O(n^2)$的算法：对于每一个点，枚举所有邻点打上标记，然后找那些没有被打上标记的点，将这些点加入到一个联通块中。如果使用链表，可以将复杂度优化到$O(n + m)$，非常的神奇。本来是非常的神秘，后来qko学长给我讲了下就变得非常神奇了 orz ...