[歐拉路]NOIP模擬題：傳送機 sent 解題報告

  【題目描述】
  刷完牙洗完臉，黃黃同學就要上課去了。可是黃黃同學每次去上課時總喜歡把校園裡面的每條路都走一遍，當然，黃黃同學想每條路也只走一遍。我們一般人很可能對一些地圖是辦不到每條路走一遍且僅走一遍的，但是黃黃同學有個傳送機，他可以任意地將一個人從一個路口傳送到任意一個路口。

可是，每傳送一次是需要耗費巨大的內力的，黃黃同學希望可以用最少的傳送次數完成遊遍校園，你能幫助他嗎 ?

因為黃黃同學只是遊歷校園，於是我們可以認為黃黃同學可以從任意點開始，到任意點結束。

【輸入文件】

輸入文件 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 。

測試數據：請聯繫 zyfworks@gmail.com

【分析】

題目的實質就是求最少添加幾條邊，使圖能一筆畫（歐拉路）

一個圖能一筆畫且最後回到起點的要求是奇點個數為０

而僅僅是一筆畫，起訖點不同的要求是奇點個數為２

【“標準”算法】

用鄰接表存儲圖，用DFS或BFS統計連通塊

連通塊間用1次傳送

連通塊內用(x div 2-1)次傳送，x為奇點個數

雖然老師說這是標準解法，但是這並不是很快，還有超時之虞。而且這種算法很不好處理掉最後一組測試數據（輸出-1的那組～）。所以，我用並查集，速度很快。

【時間複雜度】

O(n)

【我的代碼】

裸代碼RawCode

C++语言: Codee#25406

01 /*
02 *Problem: NOIP模擬題 傳送機 sent
03 *Author: Yee-fan Zhu
04 *Method: Euler-Path / Union-Find Sets / DFS
05 *Email: zyfworks@gmail.com
06 */
07 #include <cstdio>
08 #include <cstdlib>
09 #define readfile(str) freopen(str,"r",stdin)
10 #define writefile(str) freopen(str,"w",stdout)
11 using namespace std;
12
13 const int MAXN=100001;
14 int N,M;
15 int UFS[MAXN];
16 int Deg[MAXN];
17 int Num[MAXN];
18 int SingularPoint[MAXN];
19
20 int GetPnt(int n)
21 {
22     if(UFS[n]!=n)
23         UFS[n]=GetPnt(UFS[n]);
24     return UFS[n];
25 }
26
27 void init()
28 {
29     scanf("%d\n%d\n",&N,&M);
30    
31     for(int i=1;i<=N;i++)
32         UFS[i]=i;
33    
34     int a,b,ta,tb;
35     for(int i=1;i<=M;i++)
36     {
37         scanf("%d %d\n",&a,&b);
38         if(a==b)
39             continue;
40         ta=GetPnt(a);
41         tb=GetPnt(b);
42         if(ta!=tb)
43             UFS[ta]=b;
44         Deg[a]++,Deg[b]++;
45     }
46 }
47
48 void solve()
49 {
50     for(int i=1;i<=N;i++)
51     {
52         int tmp=GetPnt(i);
53         Num[tmp]++;
54         if(Deg[i]&1)
55             SingularPoint[tmp]++;
56     }
57    
58     int Top=0,Ans=0;
59     for(int i=1;i<=N;i++)
60     {
61         if(Num[i]<2)
62             continue;
63         Top++;
64         if(SingularPoint[i]<=2)
65             continue;
66         Ans+=(SingularPoint[i]-2)>>1;
67     }
68     Ans+=Top-1;
69     printf("%d\n",Ans);
70 }
71
72 int main()
73 {
74     readfile("sent.in"),writefile("sent.out");
75     init();
76     solve();
77     return 0;
78 }