题解 P1636 【Einstein学画画】

浪遏 · 2017-01-20 18:31:09 · 题解

此题其实运用一些方法就可以过了。我们可以知道，一幅图的奇数顶点必为偶数个，画一笔最多可以取消2个奇数顶点，那么除了0个外其余的图只要统计奇数点个数再除以二即可，0个的另外判断。

var n,m,i,j,x,y,max:longint;
f:array[1..1000000] of longint;
begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y);
if x>max then max:=x;
if y>max then max:=y;
f[x]:=f[x]+1;                               //判断这个点的奇偶
f[y]:=f[y]+1;
end;
j:=0;
for i:=1 to max do
if f[i] mod 2=1 then j:=j+1;         //如果是奇点个数加1
if j=0 then writeln(1)                  //奇点为0时需要特殊判断
else writeln(j div 2);                    //一笔能去除2奇点，所以除2即可
end.