題目鏈接： http://acm.nyist.net/JudgeOnline/problem.php?pid=42
或者： http://115.159.40.116/problem_show.php?pid=4654

題目大意：為歐拉通路 或 歐拉回路 即符合條件（個人觀點，測試數據也可說明我的觀點。如有錯誤還望讀者指正）
即此題為1.無向圖的歐拉通路 與? 2.無向圖的歐拉回路判斷
1.歐拉通路:圖連通；圖中只有0個或2個度為奇數的節點
2.歐拉回路:圖連通；圖中所有節點度均為偶數

兩組測試數據：

2
3 3
1 2
2 3
3 1
1 0

答案：Yes Yes

AC代碼：

#include <stdio.h> int a[1005][2]; int find(int d) {//采用并查集判斷是否為連通圖 int j = d, t;while(a[d][1] != d) d = a[d][1];//沒有父節點的即是根節點 while(a[j][1] != j) {//為了加快下一次查詢根節點的速度 t = a[j][1];a[j][1] = d;//直接將路徑上所有節點的父節點都設為根節點 j = t;}return d; } int main() {int t;scanf("%d", &t);while(t--) {int p, q, v, u, i;scanf("%d%d", &p, &q);for(i = 1; i <= p; i++) {//初始化 a[i][0] = 0;//a[i][0]存點i的度數 a[i][1] = i;//a[i][1]存父節點，a[i][1]=i表示沒有父節點 }while(q--) {scanf("%d%d", &v, &u);a[v][0]++;//統計度 a[u][0]++;if(find(v) != find(u)) a[v][1] = u;//兩者根節點不一樣時說明不在同一個連通分量，則將其連通；//在同一個連通分量直接下一次循環 }u = 0;v = 0;for(i = 1; i <= p; i++) {if(a[i][1] == i) u++; if(a[i][0]&1) v++;}//注意此處的時u>1，而不是u!=1//因為有u=0的情況（回路，或只有一個點沒有邊的通路） if(u>1 || v!=0&&v!=2) printf("No\n");else printf("Yes\n");}return 0; }

總結

以上是生活随笔為你收集整理的nyoj42一笔画问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。