本專欄持續輸出數據結構題目集，歡迎訂閱。

題目

哥尼斯堡是位于普累格河上的一座城市，它包含兩個島嶼及連接它們的七座橋，如下圖所示。

可否走過這樣的七座橋，而且每橋只走過一次？瑞士數學家歐拉(Leonhard Euler，1707—1783)最終解決了這個問題，并由此創立了拓撲學。

這個問題如今可以描述為判斷歐拉回路是否存在的問題。歐拉回路是指不令筆離開紙面，可畫過圖中每條邊僅一次，且可以回到起點的一條回路。現給定一個無向圖，問是否存在歐拉回路？

輸入格式:
輸入第一行給出兩個正整數，分別是節點數 n （1≤n≤1000）和邊數 m；隨后的 m 行對應 m 條邊，每行給出一對正整數，分別是該條邊直接連通的兩個節點的編號（節點從1到 n 編號）。

輸出格式:
若歐拉回路存在則輸出 1，否則輸出 0。

輸入樣例1:
6 10
1 2
2 3
3 1
4 5
5 6
6 4
1 4
1 6
3 4
3 6

輸出樣例1:
1

輸入樣例2:
5 8
1 2
1 3
2 3
2 4
2 5
5 3
5 4
3 4

輸出樣例2:
0

代碼

#include <stdio.h>
#include <stdlib.h>#define MAX_N 1000// 鄰接表節點結構
typedef struct Node {int vertex;struct Node* next;
} Node;// 并查集結構
typedef struct {int parent[MAX_N + 1];int rank[MAX_N + 1];
} UnionFind;// 初始化并查集
void initUnionFind(UnionFind* uf, int n) {for (int i = 1; i <= n; i++) {uf->parent[i] = i;uf->rank[i] = 1;}
}// 查找根節點并路徑壓縮
int find(UnionFind* uf, int x) {if (uf->parent[x] != x) {uf->parent[x] = find(uf, uf->parent[x]);}return uf->parent[x];
}// 合并兩個集合
void unionSets(UnionFind* uf, int x, int y) {int xRoot = find(uf, x);int yRoot = find(uf, y);if (xRoot == yRoot) return;if (uf->rank[xRoot] < uf->rank[yRoot]) {uf->parent[xRoot] = yRoot;} else if (uf->rank[xRoot] > uf->rank[yRoot]) {uf->parent[yRoot] = xRoot;} else {uf->parent[yRoot] = xRoot;uf->rank[xRoot]++;}
}int main() {int n, m;scanf("%d %d", &n, &m);// 記錄每個頂點的度數int degree[MAX_N + 1] = {0};// 初始化并查集UnionFind uf;initUnionFind(&uf, n);// 處理每條邊for (int i = 0; i < m; i++) {int u, v;scanf("%d %d", &u, &v);// 更新度數degree[u]++;degree[v]++;// 合并兩個頂點所在的集合unionSets(&uf, u, v);}// 檢查所有邊是否在同一個連通分量中int root = -1;int hasEdge = 0;for (int i = 1; i <= n; i++) {if (degree[i] > 0) {hasEdge = 1;if (root == -1) {root = find(&uf, i);} else if (find(&uf, i) != root) {// 存在多個連通分量printf("0\n");return 0;}}}// 如果沒有邊，特殊處理if (!hasEdge) {printf("0\n");return 0;}// 檢查所有頂點的度數是否為偶數for (int i = 1; i <= n; i++) {if (degree[i] % 2 != 0) {printf("0\n");return 0;}}// 所有條件滿足，存在歐拉回路printf("1\n");return 0;
}