这两题很类似，都是在补图上搜索
但是由于补图太大我们不能建出来
考虑先从一个点搜，每次搜可以搜的点，
然后维护一个链表，记录当前还没有搜过的点，搜过之后从链表中删除即可
type node=record
po,next:longint;
end; var e:array[..] of node;
l:array[..] of node;
p,q,ans:array[..] of longint;
can,v:array[..] of boolean;
s,i,n,m,len,x,y:longint; procedure add(x,y:longint);
begin
inc(len);
e[len].po:=y;
e[len].next:=p[x];
p[x]:=len;
end; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; procedure sort(l,r:longint);
var i,j,x:longint;
begin
i:=l;
j:=r;
x:=ans[(l+r) shr ];
repeat
while ans[i]<x do inc(i);
while x<ans[j] do dec(j);
if not(i>j) then
begin
swap(ans[i],ans[j]);
inc(i);
dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; procedure del(i:longint);
begin
l[l[i].po].next:=l[i].next;
if l[i].next<>- then l[l[i].next].po:=l[i].po;
end; procedure bfs;
var f,r,i,t:longint;
begin
while l[].next<>- do
begin
f:=;
r:=;
v[l[].next]:=true;
q[]:=l[].next;
del(l[].next);
t:=;
while f<=r do
begin
x:=q[f];
i:=p[x];
while i<> do
begin
can[e[i].po]:=true;
i:=e[i].next;
end;
i:=l[].next;
while i>- do
begin
if not v[i] and not can[i] then
begin
inc(r);
q[r]:=i;
del(i);
inc(t);
v[i]:=true;
end;
i:=l[i].next;
end;
i:=p[x];
while i<> do
begin
can[e[i].po]:=false;
i:=e[i].next;
end;
inc(f);
end;
inc(s);
ans[s]:=t;
end;
end; begin
readln(n,m);
for i:= to m do
begin
readln(x,y);
add(x,y);
add(y,x);
end;
for i:= to n do
begin
l[i].po:=i-;
l[i-].next:=i;
end;
l[n].next:=-;
bfs;
sort(,s);
writeln(s);
for i:= to s do
write(ans[i],' ');
writeln;
end.
1098
type node=record
po,next:longint;
end; var e:array[..] of node;
l:array[..] of node;
p:array[..] of longint;
can:array[..] of boolean;
i,n,m,x,y,len:longint; procedure add(x,y:longint);
begin
inc(len);
e[len].po:=y;
e[len].next:=p[x];
p[x]:=len;
end; procedure del(i:longint);
begin
l[l[i].po].next:=l[i].next;
if l[i].next<>- then l[l[i].next].po:=l[i].po;
end; procedure dfs(x:longint);
var i,j:longint;
begin
writeln(x);
del(x);
i:=p[x];
while i<> do
begin
can[e[i].po]:=true;
i:=e[i].next;
end;
i:=l[].next;
while i>- do
begin
if not can[i] then
begin
j:=p[x];
while j<> do
begin
can[e[j].po]:=false;
j:=e[j].next;
end;
dfs(i);
exit;
end;
i:=l[i].next;
end;
end; begin
readln(n,m);
for i:= to m do
begin
readln(x,y);
add(x,y);
add(y,x);
end;
for i:= to n do
begin
l[i-].next:=i;
l[i].po:=i-;
end;
l[n].next:=-;
dfs();
end.
1301