终于考完了期中考。。。我活着回家了！
开始写题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 #include <cstdio> 11 #include <algorithm> 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 ", ans); 80 sort(a + 1, a + ans + 1); 81 for (i = 1; i <= ans; ++i) 82 printf("%d ", a[i]); 83 return 0; 84 }