一筆畫問題

時間限制：3000 ms ?|? 內存限制：65535 KB 難度：4 描述

zyc從小就比較喜歡玩一些小游戲，其中就包括畫一筆畫，他想請你幫他寫一個程序，判斷一個圖是否能夠用一筆畫下來。

規定，所有的邊都只能畫一次，不能重復畫。

?

輸入

第一行只有一個正整數N(N<=10)表示測試數據的組數。
每組測試數據的第一行有兩個正整數P,Q(P<=1000,Q<=2000)，分別表示這個畫中有多少個頂點和多少條連線。（點的編號從1到P）
隨后的Q行，每行有兩個正整數A,B(0<A,B<P)，表示編號為A和B的兩點之間有連線。

輸出

如果存在符合條件的連線，則輸出"Yes",
如果不存在符合條件的連線，輸出"No"。

樣例輸入

2 4 3 1 2 1 3 1 4 4 5 1 2 2 3 1 3 1 4 3 4

樣例輸出

No Yes

思路：查詢奇數度點的個數，這個題不是找歐拉圖（類似的對度進行處理）；

#include<cstdio> #include<cstring> int pre[2010],p[2010]; int find(int x) {if(pre[x]==x) return x;return pre[x]=find(pre[x]); } int main() {int t,m,n,x,y;scanf("%d",&t);while(t--){int tot=0,ans=0;memset(p,0,sizeof(p));scanf("%d %d",&m,&n);for(int i=1;i<=m;i++)pre[i]=i;while(n--){scanf("%d %d",&x,&y);int fx=find(x);int fy=find(y);p[x]++;p[y]++;pre[fy]=fx;}for(int i=1;i<=m;i++){if(find(i)==i){tot++;if(tot>1)break;}if(p[i]&1)ans++;}if(tot>1){printf("No\n");continue;}if(ans==0 || ans==2)printf("Yes\n");else printf("No\n");}return 0; }

總結

以上是生活随笔為你收集整理的nyoj42一笔画问题 【欧拉回路】的全部內容，希望文章能夠幫你解決所遇到的問題。

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