Description

刷完牙洗完臉，黃黃同學就要上課去了。可是黃黃同學每次去上課時總喜歡把校園里面的每條路都走一遍，當然，黃黃同學想每條路也只走一遍。我們一般人很可能對一些地圖是辦不到每條路走一遍且僅走一遍的，但是黃黃同學有個傳送機，他可以任意地將一個人從一個路口傳送到任意一個路口。
可是，每傳送一次是需要耗費巨大的內力的，黃黃同學希望可以用最少的傳送次數完成游遍校園，你能幫助他嗎 ?
因為黃黃同學只是游歷校園，于是我們可以認為黃黃同學可以從任意點開始，到任意點結束。

Input

第一行有一個整數 N ，表示黃黃的校園里一共有多少路口。
第二行有一個整數 M ，表示路口之間有 M 條路。
后面 M 行每行兩個整數 a 、 b 表示 a 與 b 之間有一條路，且路是雙向的。

Output

只包括一個整數 s ，表示黃黃同學最少的傳送次數。

Sample Input

3
2
1 2
2 3

Sample Output

0

Hint

數據范圍：
對于 100 ％的數據，保證 N ≤ 100000 ， K ≤ 500000 ， 1 ≤ a ， b ≤ N 。

Solution

請教了數學組的大佬后才會做的...

對于一個連通塊，要完成「一筆畫」，度數為寄的點只能為0或2個，而跳一次相當于連一條邊。消除兩個寄點

所以當一個連通塊寄點數為x>2時，要化成2個時，加的邊（跳的次數）=(x-2)/2

所以bfs解決連通塊就行了

但是注意！無度數的點不要考慮，因為沒有邊要遍歷。

Code

1 #include<queue> 2 #include<vector> 3 #include<cstdio> 4 #include<cstring> 5 #include<iostream> 6 #include<algorithm> 7 #define RG register int 8 #define rep(i,a,b) for(RG i=a;i<=b;i++) 9 #define per(i,a,b) for(RG i=a;i>=b;i--) 10 #define add(x,y) e[++cnt].v=y,e[cnt].next=head[x],head[x]=cnt 11 #define inf (1<<30) 12 #define maxn 100005 13 #define maxm 500005 14 using namespace std; 15 int n,m,sid,cnt,ans; 16 int head[maxn],vis[maxn],deg[maxn]; 17 vector<int> vec[maxn]; 18 struct E{ 19 int v,next; 20 }e[maxm<<1]; 21 inline int read() 22 { 23 int x=0,f=1;char c=getchar(); 24 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 25 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 26 return x*f; 27 } 28 29 void bfs(int x) 30 { 31 int sum=0; 32 queue<int> que; 33 que.push(x),vis[x]=1; 34 RG u,v; 35 while(!que.empty()) 36 { 37 u=que.front(),que.pop(); 38 if(deg[u]&1) ++sum; 39 for(RG i=head[u];i;i=e[i].next) 40 { 41 v=e[i].v; 42 if(!vis[v]) 43 vis[v]=1,que.push(v); 44 } 45 } 46 if(sum>2) ans+=(sum-2)>>1; 47 } 48 49 int main() 50 { 51 52 n=read(),m=read(); 53 RG u,v;rep(i,1,m) u=read(),v=read(),add(u,v),add(v,u),++deg[u],++deg[v]; 54 rep(i,1,n) if(!vis[i]&&deg[i]>0) bfs(i),ans++; 55 cout<<ans-1; 56 return 0; 57 } >>點擊查看代碼<<

?

轉載于:https://www.cnblogs.com/ibilllee/p/8718378.html

總結

以上是生活随笔為你收集整理的游历校园 [COGS 614] [欧拉图]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。