Connected Components? Codeforces

CF貌似出了原题？

这几个都是一样的，输入输出都一样，就是读入一张图，要求补图的连通块个数以及各个连通块大小

可以这样搞：维护一个set表示所有当前没到过的点；一开始所有点加进去

取出set中任意点作为起始点并从set中删除，以此为起点进行bfs，直到set为空；则同一次bfs中经过的点是同一个连通块内的

从某个点u开始bfs的时候，就先找出所有原图中与u有边的点v，如果set中还有v就从set中暂时删掉v（记录下哪一些是实际删掉的）

然后当前set中所有点都是u能到达的，暴力加入bfs的队列并从set中删除；处理完这个u后，再向set中加回前面暂时删掉的点

set可以换成链表。。就O(n+m)了

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<vector>
 5 #include<list>
 6 #include<queue>
 7 using namespace std;
 8 #define fi first
 9 #define se second
10 #define mp make_pair
11 #define pb push_back
12 typedef long long ll;
13 typedef unsigned long long ull;
14 typedef pair<int,int> pii;
15 struct E
16 {
17     int to,nxt;
18 }e[4000100];
19 int f1[200100],ne;
20 list<int> li;
21 list<int>::iterator it[200100];
22 queue<int> q;
23 int n,m;
24 int tt[200100];
25 int an[200100];
26 int main()
27 {
28     int i,a,b,t,u,sz,k;
29     list<int>::iterator i1;
30     scanf("%d%d",&n,&m);
31     for(i=1;i<=m;i++)
32     {
33         scanf("%d%d",&a,&b);
34         e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;
35         e[++ne].to=a;e[ne].nxt=f1[b];f1[b]=ne;
36     }
37     for(i=1;i<=n;i++)    it[i]=li.insert(li.end(),i);
38     while(!li.empty())
39     {
40         t=li.front();li.erase(it[t]);it[t]=li.end();
41         sz=0;
42         q.push(t);
43         while(!q.empty())
44         {
45             u=q.front();q.pop();
46             sz++;
47             tt[0]=0;
48             for(k=f1[u];k;k=e[k].nxt)
49                 if(it[e[k].to]!=li.end())
50                 {
51                     tt[++tt[0]]=e[k].to;
52                     li.erase(it[e[k].to]);
53                     it[e[k].to]=li.end();
54                 }
55             while(!li.empty())
56             {
57                 t=li.front();li.erase(it[t]);it[t]=li.end();
58                 q.push(t);
59             }
60             for(i=1;i<=tt[0];i++)    it[tt[i]]=li.insert(li.end(),tt[i]);
61         }
62         an[++an[0]]=sz;
63     }
64     sort(an+1,an+an[0]+1);
65     printf("%d
",an[0]);
66     for(i=1;i<=an[0];i++)    printf("%d ",an[i]);
67     return 0;
68 }

View Code

好像也可以改成bfs到点u时，就枚举当前set中剩余的所有点v，然后判断(u,v)是否存在于原图中，如果答案为否则将v加入队列，如果用哈希表判断边是否存在则复杂度仍然O(n+m)