Post 90

Veröffentlicht am

there’s other fish in the sea

[POI2007]BIU-Offices

给出一个图（N个点，M条边），让你把此图分成尽可能多的集合，满足任意不在同一集合的点之间都有边相连。

$(2 \le n \le 100\ 000, 1 \le m \le 2\ 000\ 000)$

题解

先想到一个最坏是$O(n^2)$的做法。

map存边，可以$O(logn)$的查询两点间有没有边。

枚举点对，没有边就并查集合并。

这样最多合并$n$次，但是由于无用的枚举可能最坏依然是$O(n^2)$。

只需要加一个优化，只要一个点已经合并过了，就不再合并。但是一个点必须枚举所有点来合并。

这样复杂度就是非常科学的$O(nlogn)$

准备分析一下只路径压缩的并查集的复杂度。

哦对了，这样只得了60分，可能复杂度的问题在于还是重复合并了。

说到底还是我根本不会证正确性。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#define maxn 100005
int head[maxn] , n , ans , m , f[maxn] , c[maxn];
std::vector<int> s;
std::map<int,int> e[maxn];
int find(int x){
	return f[x] == x ? x : f[x] = find(f[x]);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= n ; ++i)
		f[i] = i;
	for(int i = 1 ; i <= m ; ++i)
	{
		int x , y;
		scanf("%d%d",&x,&y);
		e[x][y] = e[y][x] = 1;
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		if(find(i) != i) continue;
		for(int j = 1 ; j <= n ; ++j)
		{
			if(!e[i][j]) {
				f[find(i)] = find(j);
		//		break;
			}
		}
	}
	for(int i = 1 ; i <= n ; ++i)
		c[find(i)] ++ ;
	for(int i = 1 ; i <= n ; ++i)
		if(c[i])
			++ans , s.push_back(c[i]);
	printf("%d\n",ans);
	std::sort(s.begin() , s.end());
	for(int i = 0 ; i < (int)s.size() ; ++i)
		printf("%d ",s[i]);
}

正解是一个队列，不过感觉+按秩合并也能过。

突然发现可以用邻接表emmm，然后就80了，本来就没必要用map 233.

然后我要是加玄学优化，#4就WA，如果不加#5就T。

遇到这种情况就疯狂分析吧。80考场也行

CF920E Connected Components?

题意翻译

给出一个$n $个点，$\frac{n(n-1)}{2}-m$的无向图，问图中有多少连通分量以及每个连通分量有多少点

输入中给出$m$对点，表示这一对点之间没有边，否则就是有边

输出连通分量的个数以及每个连通分量有多少个点

$1<=n<=200000 , m \leq 200000$

题解

首先明确概念，连通分量$G$的等价条件是子图$G$任意两点均有路径可达。

因此这道题只需要维护度数即可。。。只要度数是$n-1$就意味着真实图中是孤立点，ans++。

写了说不定FST

假的，又不是只有孤立点。

突然发现还要求输出每个联通分量的大小。

那么我们可以用并查集在$O(n^2logn)$解决。。

正解和上面一道题好像很像，不管了。