652
技術社區[雲棲]
NYOJ42一筆畫問題
一筆畫問題
時間限製：3000 ms 內存限製：65535 KB
難度：4
描述
zyc從小就比較喜歡玩一些小遊戲，其中就包括畫一筆畫，他想請你幫他寫一個程序，判斷一個圖是否能夠用一筆畫下來。
規定，所有的邊都隻能畫一次，不能重複畫。
輸入
第一行隻有一個正整數N(N=10)表示測試數據的組數。
每組測試數據的第一行有兩個正整數P,Q(P=1000,Q=2000)，分別表示這個畫中有多少個頂點和多少條連線。（點的編號從1到P）
隨後的Q行，每行有兩個正整數A,B(0A,BP)，表示編號為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.奇數點的個數要麼為2要麼為0，這是歐拉路的判斷，如果奇數點的個數為2，說明有一個開頭節點和一個結尾節點，
如果奇數點的個數為0，那麼沒有開頭和結尾，是一個完全的環，依然符合一筆畫，剩下的情況一定不符合題意。
接下來就是用DFS染色法把能通過的所有路徑全都染色，剩下的沒有被染色的則是獨立點，則就不能一筆畫。
AC代碼：
#include<stdio.h>
#include<string.h>
struct node//創建一個路徑計數結構體
{
int path[1100];
int len;
}a[1100];
int jar[1100];
void DFS(int n)
{
int last;
while(a[n].len!=0)//深入搜索 a[n]每一個能連接的點
{
last=a[n].path[a[n].len-1];//傳回最後一個數據
jar[last]=1;
a[n].len--;//刪除最後一個數據
DFS(last);//跳向下一個點進行搜索
}
}
int main()
{
int i,j,T,n,m,x,y,num,size,flag;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
for(i=0;i<m;i++)
{
scanf("%d %d",&x,&y);
a[x].path[a[x].len++]=y;//a[x]末尾添加y
a[y].path[a[y].len++]=x;//a[y]末尾添加x
}
num=0;
for(i=1;i<=n;i++)
{
size=a[i].len;
if(size%2!=0)//檢查每一個點相對於其它點的連通性
num++;
}
memset(jar,0,sizeof(jar));
jar[1]=1;//先標記第一個點直接能通過
DFS(1);
flag=1;
for(i=1;i<=n;i++)
if(jar[i]==0)//存在點一個點，其與任意一點都不相連
{
flag=0;
break;
}
if(num>2||num==1)//當odd大於2時，說明有的點斷層了，當odd等於1時，說明出現了部分環（等於0時是完全環，符合一筆畫）
flag=0;
if (flag==1)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
最後更新：2017-04-03 12:56:30