传送机(sent.pas/e/cpp)
【问题描述】
刷完牙洗完脸，黄黄同学就要上课去了。可是黄黄同学每次去上课时总喜欢把校园里面的每条路都走一遍，当然，黄黄同学想每条路也只走一遍。我们一般人很可能对一些地图是办不到每条路走一遍且仅走一遍的，但是黄黄同学有个传送机，他可以任意地将一个、人从一个路口传送到任意一个路口。
可是，每传送一次是需要耗费巨大的内力的，黄黄同学希望可以用最少的传送次数完成游遍校园，你能帮助他吗?
因为黄黄同学只是游历校园，于是我们可以认为黄黄同学可以从任意点开始，到任意点结束。
【输入文件】
输入文件sent.in的第一行有一个整数N，表示黄黄的校园里一共有多少路口。
第二行有一个整数M，表示路口之间有M条路。
后面M行每行两个整数a、b表示a与b之间有一条路，且路是双向的。
【输出文件】
输出文件sent.out只包括一个整数s，表示黄黄同学最少的传送次数。
【样例输入】
3
2
1 2
2 3
【样例输出】
0
【数据范围】
对于100％的数据，保证N≤100000，K≤500000，1≤a，b≤N。
【时限】
ls
题目的实质就是求最少添加几条边，使图能一笔画（欧拉路）
一个图能一笔画且最后回到起点的要求是奇点个数为０
而仅仅是一笔画，起讫点不同的要求是奇点个数为２
奇点个数一定是偶数
原先只统计奇点个数，没有考虑连通块的问题，做题还是不太认真，考虑没有全面
＂正规＂的做法是用链表存储，用ＢＦＳ统计连通块
program Jackchen;
type tree=^node;
node=record
val:longint;
link:tree;
end;
var n,m,i,j,x,y,t,v,s,cv:longint;
c:array[1..100000] of tree;
team,num:array[1..100000] of longint;
vis:array[1..100000] of boolean;
h,d:longint;
ttree:tree;
tot1,tot,ans:longint;
procedure insert(a,b:longint);
var ttree:tree;
begin
new(ttree);
ttree^.val:=b;
ttree^.link:=c[a];
c[a]:=ttree;
end;
begin
assign(input,'sent.in');assign(output,'sent.out') ;
reset(input); rewrite(output);
fillchar(num,sizeof(num),0) ;
readln(n); readln(m);
for i:=1 to m do
begin
readln(x,y);
if x=y then continue;
insert(x,y);
insert(y,x);
inc(num[x]) ; inc(num[y]);
end;
fillchar(vis,sizeof(vis),true);
ans:=0; tot1:=0;
for i:=1 to n do
if vis[i] then
begin
h:=0; d:=1;
team[1]:=i; vis[i]:=false; tot:=0;
if odd(num[i]) then inc(tot);
repeat
inc(h); v:=team[h]; ttree:=c[v];
while ttree<>nil do
begin
cv:=ttree^.val;
if vis[cv] then
begin
vis[cv]:=false;
inc(d);
team[d]:=cv;
if odd(num[cv]) then inc(tot);
end;
ttree:=ttree^.link;
end;
until h>=d;
if d<=1 then continue;
inc(tot1);
if tot>2 then ans:=ans+(tot-2)div 2;
end;
ans:=ans+tot1-1;
writeln(ans);
close(input); close(output);
end.
结果老师的评测能过，机房的celeron 1.7G超了
感谢林宇鹏大牛提供的并查集思路，原先我还担心递归会堆栈溢出（Ｎ＝１０００００），结果给出的数据全部能秒过
program fdfdf;
var n,i,j,m,x,y,f1,f2,tot1,ans:longint;
f,num,oddn,c:array[1..100000] of longint;
function dfs(v:longint):longint;
begin
if v<>f[v] then f[v]:=dfs(f[v]);
dfs:=f[v];
end;
begin
assign(input,'sent.in');assign(output,'sent.out');
reset(input); rewrite(output);
readln(n);
readln(m);
fillchar(c,sizeof(c),0);
for i:=1 to n do f[i]:=i;
for i:=1 to m do
begin
readln(x,y);
if x=y then continue;
f1:=dfs(x); f2:=dfs(y);
if f1<>f2 then
f[f1]:=y;
inc(c[x]); inc(c[y]);
end;
fillchar(num,sizeof(num),0) ;
fillchar(oddn,sizeof(oddn),0);
for i:=1 to n do
begin
f1:=dfs(i);
inc(num[f1]);
if odd(c[i]) then inc(oddn[f1]);
end;
tot1:=0; ans:=0;
for i:=1 to n do
if num[i] >1 then
begin
if oddn[i]>2 then
ans:=ans+(oddn[i]-2) div 2;
inc(tot1);
end;
writeln(ans+tot1-1);
close(input); close(output);
end.
