这两题很类似，都是在补图上搜索
但是由于补图太大我们不能建出来
考虑先从一个点搜，每次搜可以搜的点，
然后维护一个链表，记录当前还没有搜过的点，搜过之后从链表中删除即可
1 type node=record 2 po,next:longint; 3 end; 4 5 var e:array[0..4000010] of node; 6 l:array[0..100010] of node; 7 p,q,ans:array[0..100010] of longint; 8 can,v:array[0..100010] of boolean; 9 s,i,n,m,len,x,y:longint; 10 11 procedure add(x,y:longint); 12 begin 13 inc(len); 14 e[len].po:=y; 15 e[len].next:=p[x]; 16 p[x]:=len; 17 end; 18 19 procedure swap(var a,b:longint); 20 var c:longint; 21 begin 22 c:=a; 23 a:=b; 24 b:=c; 25 end; 26 27 procedure sort(l,r:longint); 28 var i,j,x:longint; 29 begin 30 i:=l; 31 j:=r; 32 x:=ans[(l+r) shr 1]; 33 repeat 34 while ans[i]j) then 37 begin 38 swap(ans[i],ans[j]); 39 inc(i); 40 dec(j); 41 end; 42 until i>j; 43 if l -1 then l[l[i].next].po:=l[i].po; 51 end; 52 53 procedure bfs; 54 var f,r,i,t:longint; 55 begin 56 while l[0].next<>-1 do 57 begin 58 f:=1; 59 r:=1; 60 v[l[0].next]:=true; 61 q[1]:=l[0].next; 62 del(l[0].next); 63 t:=1; 64 while f<=r do 65 begin 66 x:=q[f]; 67 i:=p[x]; 68 while i<>0 do 69 begin 70 can[e[i].po]:=true; 71 i:=e[i].next; 72 end; 73 i:=l[0].next; 74 while i>-1 do 75 begin 76 if not v[i] and not can[i] then 77 begin 78 inc(r); 79 q[r]:=i; 80 del(i); 81 inc(t); 82 v[i]:=true; 83 end; 84 i:=l[i].next; 85 end; 86 i:=p[x]; 87 while i<>0 do 88 begin 89 can[e[i].po]:=false; 90 i:=e[i].next; 91 end; 92 inc(f); 93 end; 94 inc(s); 95 ans[s]:=t; 96 end; 97 end; 98 99 begin100 readln(n,m);101 for i:=1 to m do102 begin103 readln(x,y);104 add(x,y);105 add(y,x);106 end;107 for i:=1 to n do108 begin109 l[i].po:=i-1;110 l[i-1].next:=i;111 end;112 l[n].next:=-1;113 bfs;114 sort(1,s);115 writeln(s);116 for i:=1 to s do117 write(ans[i],' ');118 writeln;119 end.
1 type node=record 2 po,next:longint; 3 end; 4 5 var e:array[0..2000010] of node; 6 l:array[0..100010] of node; 7 p:array[0..100010] of longint; 8 can:array[0..100010] of boolean; 9 i,n,m,x,y,len:longint;10 11 procedure add(x,y:longint);12 begin13 inc(len);14 e[len].po:=y;15 e[len].next:=p[x];16 p[x]:=len;17 end;18 19 procedure del(i:longint);20 begin21 l[l[i].po].next:=l[i].next;22 if l[i].next<>-1 then l[l[i].next].po:=l[i].po;23 end;24 25 procedure dfs(x:longint);26 var i,j:longint;27 begin28 writeln(x);29 del(x);30 i:=p[x];31 while i<>0 do32 begin33 can[e[i].po]:=true;34 i:=e[i].next;35 end;36 i:=l[0].next;37 while i>-1 do38 begin39 if not can[i] then40 begin41 j:=p[x];42 while j<>0 do43 begin44 can[e[j].po]:=false;45 j:=e[j].next;46 end;47 dfs(i);48 exit;49 end;50 i:=l[i].next;51 end;52 end;53 54 begin55 readln(n,m);56 for i:=1 to m do57 begin58 readln(x,y);59 add(x,y);60 add(y,x);61 end;62 for i:=1 to n do63 begin64 l[i-1].next:=i;65 l[i].po:=i-1;66 end;67 l[n].next:=-1;68 dfs(1);69 end.