NYoj-42-一筆畫問題-DFS

NYoj-42-一筆畫問題-DFS

一筆畫問題

描述

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

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

輸入

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

如果存在符合條件的連線，則輸出"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
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int line[1010];   //統計各個結點的度 
int visit[1010];   //記錄訪問過的點 
int G[1010][1010]; //記錄i,j是否相連 
int vertex,edge; 
void DFS(int i)    //判斷是否連通 
{
	//int v=i;
	visit[i]=1;    //i 已訪問   
	for(int v=0;v<=vertex;v++) 
	{
		if(v!=i && G[i][v] &&!visit[v]) //找一個！=i /與i連通 /沒有訪問過得點 
		    DFS(v);//繼續從這個點開始往下訪問 
	} 
}
int main()
{
	int T,x,y,count,flag;
	while(~scanf("%d",&T))
	{
		while(T--)
		{
			count=0;
			flag=1;
			scanf("%d %d",&vertex,&edge); //頂點數和邊數 
			memset(line,0,sizeof(line));
			memset(visit,0,sizeof(visit));
			memset(G,0,sizeof(G));
			for(int i=1;i<=edge;i++)    
			{
				scanf("%d%d",&x,&y); 
				G[x][y]=G[y][x]=1; 
				line[x]++;    //該點的度 
				line[y]++;    
			}
			DFS(0);
			for(int i=0;i<=vertex;i++)
			{
				G[i][i]=1;
				if(!visit[i])
				   flag=0;
				if(line[i]%2!=0)
				   count++;
			}
			if(flag)
			{
				if(count==2||count==0)
				{
					printf("Yes\n");
				}
				else
				{
					printf("No\n");
				}
			}
			else
			{
				printf("No\n");
			}
		}
	} 
	return 0;
}