這題是點雙連通分量，我一開始寫成邊的……
首先點雙連通分量可能重疊……(1,2) (2,3) (3,1) (3,4) (4,5) (5,6) (3.6)
這時有（1，2，3）和（3，4，5，6）兩組雙連通分量
故一定要在Tarjen裡判……另外Stack存邊時注意特判(Stack不能為空）
當dfs[k]<=low[i] 時 就找到了點雙連通分量 （這是點雙連通）
請注意在推送（k，i）後遍歷得到的一堆邊(包括（k，i）)組成了一組點雙連通分量
兩個重要定理：
（1） 如果一個雙連通分量內的某些頂點在一個奇圈中（即雙連通分量含有奇圈），那麼這個雙連通分量的其他頂點也在某個奇圈中；
（2） 如果一個雙連通分量含有奇圈，則他必定不是一個二分圖。反過來也成立，這是一個充要條件。
[delphi]
Program P2942;
const
maxn=1050;
maxm=1000000;
Var
n,m,i,j,x,y:longint;
b:array[1..maxn,1..maxn] of boolean;
color,c,dfs,low:array[1..maxn] of longint;
attend,flag:array[1..maxn] of boolean;
size,time,totssc:longint;
stack:array[0..maxm,1..2] of longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
function is_Binary(k,col:longint):boolean;
var
i,j:longint;
begin
color[k]:=col;
for i:=1 to n do
if (flag[i]) and (b[k,i]) then
begin
if color[i]=0 then
begin
if not(is_binary(i,3-col)) then exit(false);
end
else
if color[k]=color[i] then exit(false);
end;
exit(true);
end;
procedure tarjen(k,father:longint);
var
i,j:longint;
begin
inc(time);
dfs[k]:=time;
low[k]:=time;
c[k]:=1;
for i:=1 to n do
if (b[k,i]) and (dfs[k]>dfs[i]) and (i<>father) then
begin
if dfs[i]=0 then
begin
inc(size);
stack[size,1]:=k;
stack[size,2]:=i;
tarjen(i,k);
low[k]:=min(low[k],low[i]);
if dfs[k]<=low[i] then
begin
fillchar(flag,sizeof(flag),false);
fillchar(color,sizeof(color),false);
while (size>0) do
begin
flag[stack[size,1]]:=true;
flag[stack[size,2]]:=true;
dec(size);
if (stack[size+1,1]=k) and (stack[size+1,2]=i) then break;
end;
if not(is_binary(k,1)) then
begin
for j:=1 to n do
if flag[j] then attend[j]:=true;
end;
end;
end
else
if c[i]=1 then low[k]:=min(low[k],dfs[i]);
end;
c[k]:=2;
end;
function main:longint;
var
i,j,tot:longint;
begin
fillchar(dfs,sizeof(dfs),0);
fillchar(low,sizeof(low),0);
fillchar(c,sizeof(c),0);
fillchar(attend,sizeof(attend),false);
fillchar(flag,sizeof(flag),false);
fillchar(color,sizeof(color),0);
fillchar(stack,sizeof(stack),0);
size:=0;time:=0;
for i:=1 to n do
if (dfs[i]=0) then
begin
tarjen(i,0);
end;
tot:=0;
for i:=1 to n do if attend[i] then inc(tot);
exit(n-tot);
end;
begin
while not seekeof do
begin
read(n,m);
if (n=0) and (m=0) then break;
fillchar(b,sizeof(b),true);
for i:=1 to n do b[i,i]:=false;
for i:=1 to m do
begin www.2cto.com
read(x,y);
b[x,y]:=false;
b[y,x]:=false;
end;
writeln(main);
end;
end.
