一筆畫問題

時間限制：3000ms ?|? 內(nèi)存限制：65535KB 難度：4 描述

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

規(guī)定，所有的邊都只能畫一次，不能重復(fù)畫。

?

?

輸入

第一行只有一個正整數(shù)N(N<=10)表示測試數(shù)據(jù)的組數(shù)。
每組測試數(shù)據(jù)的第一行有兩個正整數(shù)P,Q(P<=1000,Q<=2000)，分別表示這個畫中有多少個頂點和多少條連線。（點的編號從1到P）
隨后的Q行，每行有兩個正整數(shù)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

?

數(shù)學(xué)家歐拉找到一筆畫的規(guī)律是：　　■⒈凡是由偶點組成的連通圖，一定可以一筆畫成。畫時可以把任一偶點為起點，最后一定能以這個點為終點畫完此圖。　　■⒉凡是只有兩個奇點的連通圖（其余都為偶點），一定可以一筆畫成。畫時必須把一個奇點為起點，另一個奇點終點。　　■⒊其他情況的圖都不能一筆畫出。(有偶數(shù)個奇點除以二便可算出此圖需幾筆畫成。)根據(jù)歐拉總結(jié)的規(guī)律，我們只需要1、判斷圖是否聯(lián)通2、判斷點是奇點的個數(shù)，就可以了。

#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; /*標(biāo)記已訪問該點*/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組數(shù)據(jù)*/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))) //圖連通且有兩個或沒有奇數(shù)點 printf("Yes\n");elseprintf("No\n");}return 0; }

???????

總結(jié)

以上是生活随笔為你收集整理的nyoj 42 一笔画问题 （搜索+队列）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。