b924 - kevin 愛畫畫

🔗 前往 ZeroJudge 原題

題目描述

題目要求判斷給定的無向圖是否為一筆畫圖（Eulerian path 或 Eulerian circuit）。圖由 n 個點和 m 條邊組成，輸入給定邊的連接關係。

解題思路

根據 Euler 定理，一個無向圖存在 Euler path 的條件是：

1. 圖是連通的（題目保證）。
2. 圖中奇度數節點的數量為 0 或 2。

程式碼中，a[i] 記錄了第 i+1 個節點的度數。遍歷所有邊，增加相應節點的度數。然後，統計奇度數節點的數量 s。如果 s 大於 2，則不可能存在 Euler path，輸出 "NO"。如果 s 不等於 0 或 2，則輸出 "NO"。否則，輸出 "YES"。

複雜度分析

• 時間複雜度: O(m + n)
• 空間複雜度: O(n)

程式碼

#include <stdio.h>
int main(){
	int n,m;
	while(scanf("%d%d",&n,&m)>0){
		int a[n]={0},x,y,s=0,ans=0;
		while(m--){
			scanf("%d%d",&x,&y);
			++a[x-1];
			++a[y-1];
		}
		for(int i=0;i<n;++i){
			if(a[i]%2){
				++s;
				if(s>2)
					ans=1;
			}
		}
		if(ans||(s!=2&&s!=0))
			printf("NO\n");
		else
			printf("YES\n");
	}
}