var
n,p,i,j,t,l,v,ans:longint;
from,d,f,r,s:array[0..301]of longint;
a,b:array[0..10000]of longint;
function shu(x:longint):longint;
var
k:longint;
begin
if s[x]<>-1 then exit(s[x]);
s[x]:=0;
for k:=1 to n do
if from[k]=x then s[x]:=s[x]+shu(k);
s[x]:=s[x]+1;
exit(s[x]);
end;
procedure dfs(y:longint);
var
g:longint;
begin
f[y]:=0;
if r[y]=0 then exit;
for g:=1 to n do
if from[g]=y then dfs(g);
end;
begin
readln(n,p);
for i:=1 to n do
s[i]:=-1;
for i:=1 to p do
readln(a[i],b[i]);
for i:=1 to n do
d[i]:=0;
d[1]:=1;
for i:=1 to n do
r[i]:=0;
for i:=1 to p do
begin
if d[a[i]]=0 then begin
d[a[i]]:=d[b[i]]+1;
from[a[i]]:=b[i];
inc(r[b[i]]);
end
else
if d[b[i]]=0 then begin
d[b[i]]:=d[a[i]]+1;
from[b[i]]:=a[i];
inc(r[a[i]]);
end;
end;
t:=0;
for i:=1 to n do
if d[i]>t then t:=d[i];
for i:=1 to n do
if d[i]=t then s[i]:=1;
for i:=1 to n do
f[i]:=1;
for i:=2 to t do
begin
l:=-2;
for j:=1 to n do
if d[j]=i then
if f[j]=1 then
if shu(j)>l then begin
v:=j;
l:=shu(j);
end;
dfs(v);
end;
ans:=0;
for i:=1 to n do
if f[i]=1 then inc(ans);
writeln(ans);
end.
过倒数第二个测试点的时候，应该是55，我输出56。求解...
很自然的思路，选取每一层最多的点，删去。。。
但这是错的，看看倒数第二个点多少人WA（输出56）就知道了，正确的做法是，搜索每一层删掉的，然后回溯。。
至于优化，快排一下，只搜前几个就OK了。。
/*
ID:echooat1
LANG:C++
TASK:
*/
/*
* File: main.cpp
* Author: Oatmeal
* Created on 2010年8月6日, 下午4:44
*/
/*
test.in:
7 6
1 2
1 3
2 4
2 5
3 6
3 7
test.out:
3
test ok?(Y/N) Y
*/
#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
void find(long);
long a[400][400]={0},c[400]={0},s[400]={0};
long inp[400]={0},p[400]={0};
long ans=19940522,temp=1;
long n,m;
int comp(const void*,const void*);
int main(int argc,char** argv){
ifstream fin("1.in");
fin >>n>>m;
c[0]=400;
for(long i=1;i<=m;i++){
long x,y;
fin >>x>>y;
if(x>y){long b=0;b=x;x=y;y=b;}
p[y]=x;
inp[x]++;
a[x][++s[x]]=y;
}
for(long i=1;i<=n;i++)
for(long j=1;j<=n;j++)
if(!inp[j]){inp[p[j]]--;c[p[j]]+=c[j]+1;inp[j]=521;}
find(1);
cout <<ans<<endl;
fin.close();
return 0;
}
void find(long u){
long ma=0;long o=0,ll=0,mm;
long k=0;
qsort(a[u],s[u]+1,sizeof(a[u][0]),comp);
if(s[u]!=1)
k=a[u][2];else k=a[u][1];
o=a[u][1];
for(long i=1;i<=s[u];i++){
if(a[u][i]!=o&&a[u][i]!=k)
for(long j=1;j<=s[a[u][i]];j++){
a[k][++s[k]]=a[a[u][i]][j];
ll++;
}
}
--temp+=s[u];
//if(!ma)ans++;
if(s[k]){mm=temp;
find(k); temp=mm;s[k]-=ll;}else if(temp<ans)ans=temp;
ll=0;
k=a[u][1];
if(s[u]<2)return;
o=a[u][2];
for(long i=1;i<=s[u];i++){
if(a[u][i]!=o&&a[u][i]!=k)
for(long j=1;j<=s[a[u][i]];j++){
a[k][++s[k]]=a[a[u][i]][j];
ll++;
}
}
if(s[k]){mm=temp;
find(k);temp=mm;s[k]-=ll;}else if(temp<ans)ans=temp;
}
int comp(const void* a,const void* b){
long l1=*(long *)b;long l2=*(long *)a;
return c[l1]-c[l2];
}