描述 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 數學家歐拉找到一筆畫的規律是： ■⒈凡是由偶點組成的連通圖，一定可以一筆畫成。畫時可以把任一偶點為起點，最後一定能以這個點為終點畫完此圖。 ■⒉凡是只有兩個奇點的連通圖（其余都為偶點），一定可以一筆畫成。畫時必須把一個奇點為起點，另一個奇點終點。 ■⒊其他情況的圖都不能一筆畫出。(有偶數個奇點除以二便可算出此圖需幾筆畫成。) 根據歐拉總結的規律，我們只需要1、判斷圖是否聯通2、判斷點是奇點的個數，就可以了。 #include<stdio.h> #include<string.h> #include<queue> using namespace std; int map[1005][1005],vis[1005]; int i,p,q,odd,cnt; void bfs(int n) { int t,num; queue<int>s; s.push(1); /*從1開始*/ vis[1]=1; /*標記已訪問該點*/ while(!s.empty()) /*隊列非空*/ { t=s.front(); s.pop(); cnt++; num=0; for(i=1;i<=n;i++) { if(map[t][i]!=0) /*這兩點之間有連線*/ { if(vis[i]==0) /*i點還未訪問*/ { s.push(i); vis[i]=1; } num++; } } if(num%2==1) odd++; } } int main() { int j,a,b,m; scanf("%d",&m);/*m組數據*/ while(m--) { odd=cnt=0; memset(vis,0,sizeof(vis)); /*初始化都沒有訪問*/ memset(map,0,sizeof(map));/*初始化都沒有連線*/ scanf("%d%d",&p,&q); for(i=0;i<q;i++) { scanf("%d%d",&a,&b); map[a][b]=1; map[b][a]=1; /*建立圖表*/ } bfs(p); if((p==cnt)&&((odd==0)||(odd==2))) //圖連通且有兩個或沒有奇數點 printf("Yes\n"); else printf("No\n"); } return 0; }
