终于考完了期中考。。。我活着回家了！
开始写题ing》》》》》
这道题嘛。。。先转化成补图，然后问题就变成求连通块个数。
但是会T，是因为点多而且是稠密图。。。
于是就用链表优化就好啦~
1 /************************************************************** 2 Problem: 1098 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:5708 ms 7 Memory:34108 kb 8 ****************************************************************/ 9 10 #include11 #include 12 13 using namespace std;14 const int N = 100005;15 const int M = 4000005;16 17 struct edges{18 int next, to;19 edges() {}20 edges(int a, int b) : next(a), to(b) {}21 }e[M];22 23 int n, m, ans;24 int first[N], tot;25 int q[N], l, r;26 int pre[N], next[N], a[N];27 bool to[N];28 29 inline int read(){30 int x = 0;31 char ch = getchar();32 while (ch < '0' || ch > '9')33 ch = getchar();34 while (ch >= '0' && ch <= '9'){35 x = x * 10 + ch - '0';36 ch = getchar();37 }38 return x;39 }40 41 void add_Edges(int x, int y){42 e[++tot] = edges(first[x], y), first[x] = tot;43 e[++tot] = edges(first[y], x), first[y] = tot;44 }45 46 inline void del(int x){47 int tmp = pre[x];48 next[tmp] = next[x];49 pre[next[x]] = tmp;50 }51 52 void bfs(int p){53 q[0] = p;54 int now, x;55 for (l = r = 0; l <= r; ++l){56 ++a[ans];57 now = q[l];58 for (x = first[now]; x; x = e[x].next)59 to[e[x].to] = 1;60 for (x = next[0]; x <= n; x = next[x])61 if (!to[x])62 del(x), q[++r] = x;63 for (x = first[now]; x; x = e[x].next)64 to[e[x].to] = 0;65 }66 }67 68 int main(){69 n = read(), m = read();70 int i, x, y;71 for (i = 0; i <= n; ++i)72 next[i] = i + 1, pre[i + 1] = i;73 for (i = 1; i <= m; ++i){74 x = read(), y = read();75 add_Edges(x, y);76 }77 for (i = next[0]; i <= n; i = next[0])78 del(i), ++ans, bfs(i);79 printf("%d\n", ans);80 sort(a + 1, a + ans + 1);81 for (i = 1; i <= ans; ++i)82 printf("%d ", a[i]);83 return 0;84 }