luogu3452-POI

发表于 | 分类于

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

很明显最多的集合数就是联通块的数量，所以我们只要求出联通块的数量以及每个联通块的大小就行了。我第一个想到的做法是$n^2$建出反图，然后bfs。然后看到n的范围(2<=n<=100 000)果断放弃。然后就放着了。今天又碰到，在网上查了查题解，发现其实这道题就是个链表优化的暴力。。。。把n个点放到一个链表里，每次取表头，把不和它相连的点和它自己在链表里删掉并加进一个队列进行bfs，重复这个过程，直到链表为空，我们就得到了联通块的个数，每个联通块的大小可以在bfs时求得。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int lst[100005],pre[100005];
int tot,had[100005],nxt[40000006],point[4000006];
int n,m;
inline void add(int x,int y)
{
    tot++;
    point[tot]=y;
    nxt[tot]=had[x];
    had[x]=tot;
    tot++;
    point[tot]=x;
    nxt[tot]=had[y];
    had[y]=tot;
}
inline void del(int x)
{
    lst[pre[x]]=lst[x];
    pre[lst[x]]=pre[x];
}
int ans=0,a[100005];
int que[100005];
bool vis[100005];
int h,t;
inline void bfs(int x)
{
    h=t=0;
    que[t++]=x;
    while(t!=h)
    {
        int x=que[h++];
        a[ans]++;
        for(int i=had[x];i;i=nxt[i])
            vis[point[i]]=1;
        for(int i=lst[0];i<=n;i=lst[i])
        {
            if(vis[i])
            {
                vis[i]=0;
                continue;
            }
            del(i);
            que[t++]=i;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)
        lst[i]=i+1;
    for(int i=1;i<=n+1;i++)
        pre[i]=i-1;
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(int i=lst[0];i<=n;i=lst[0])
    {
        del(i);
        ans++;
        bfs(i);
    }
    sort(a+1,a+1+ans);
    printf("%d\n",ans);
    for(int i=1;i<=ans;i++)
        printf("%d ",a[i]);
    return 0; 
}