返回列表 發帖

Rank: 9Rank: 9Rank: 9
1# 跳轉到 » 倒序看帖
打印
tT
may發表於 5 天前 22:00 | 只看該作者

資料結構 402 一筆畫遊戲(易)

資料結構 402 一筆畫遊戲
1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。

2. 設計說明：
(1) 尤拉路徑是圖論（Graph Theory）中被廣為人知的一個經典問題，又被稱為「一筆畫問題」，起源於哥尼斯堡七橋問題；數學家尤拉（Euler）在 1736 年解開了七橋問題並提出相關結論與定理：如果能夠從圖上某一點當作起點出發，找出一條路徑可以通過圖上所有邊恰好一次，就好像用畫筆可以連續地畫過該圖形的所有邊，該路徑就稱為「尤拉路徑（Euler path）」。

(2) 以下是尤拉對於一筆畫問題的重點結論：
「一個連通圖中，所有節點的分支度都是偶數，或只有 2 個節點的分支度是奇數，則該圖就可以用一筆畫完成；否則無法一筆畫。」

(3) 一個無向圖（Undirected Graph）通常表示為 G=(V,E)，其中 V 為節點（Vertex）的集合，E 為邊（Edge）的集合，且任一個邊是由兩個相連接的節點所構成，當標示為 (a,b) 即表示節點 a 與 b 之間有邊連接。

(4) 請設計一支程式，可以讀取一個無向圖的資料（邊的列表），然後判斷該圖形是否能夠一筆畫完成，並輸出圖形的相鄰矩陣結果（注意：題目給的圖形一定是「連通圖」）。

提示：任一節點的「分支度（Degree）」為該節點連接的邊數、亦即是對外所連接的節點數。

提示：「連通圖（Connected Graph）」中的任兩個節點必存在一條路徑相通；反之則為「非連通圖」。

提示：可使用「二維陣列（Two-Dimensional Array）」資料結構來實作「相鄰矩陣（Adjacency Matrix）」以紀錄圖形中節點與節點的關係（邊）。

3. 輸入輸出：
輸入說明
第 1 列：包含兩個正整數 M、N，並以半形空白間隔，其中 M 為節點數、N 為邊數。
第 2~N+1 列：每一列包含兩個正整數 a、b，並以半形空白間隔，代表圖形的某一個邊連接節點 a 與 b，且 1 ≤ a, b ≤ M。

輸出說明
第 1 列：若圖形可以「一筆畫完成」，則輸出「YES」；否則輸出「NO」。
第 2~M+1 列：輸出圖形的相鄰矩陣，共有 M 列由 0 與 1 所構成的資料列，每一列有 M 個數字，請使用「1」表示列、行相對應的節點之間有邊；使用「0」表示沒有對應邊的存在，每個數字之間須以半形空白間隔。

範例輸入1
3 3
1 2
1 3
3 2
範例輸出1
YES
0 1 1
1 0 1
1 1 0
範例輸入2
5 8
1 2
1 3
1 4
1 5
2 5
3 2
3 4
5 4
範例輸出2
NO
0 1 1 1 1
1 0 1 0 1
1 1 0 1 0
1 0 1 0 1
1 1 0 1 0
收藏 分享
May

Rank: 9Rank: 9Rank: 9
2#
may發表於 5 天前 22:27 | 只看該作者
  1. #include <bits/stdc++.h>
  2. //#include <iostream>
  3. //#include <vector>

  5. using namespace std;

  7. int main() {
  8.     int M, N;
  9.     cin >> M >> N;
  10.    
  11.     vector<vector<int>> adjMatrix(M, vector<int>(M, 0)); // 建立 M x M 的鄰接矩陣
  12.     vector<int> degree(M, 0); // 紀錄每個節點的度數
  13.    
  14.     for (int i = 0; i < N; i++) {
  15.         int a, b;
  16.         cin >> a >> b;
  17.         a--; b--; // 轉換為 0-based index
  18.         adjMatrix[a][b] = 1;
  19.         adjMatrix[b][a] = 1;
  20.         degree[a]++;
  21.         degree[b]++;
  22.     }
  23.    
  24.     // 判斷是否滿足 Euler Path 條件
  25.     int oddCount = 0;
  26.     for (int i = 0; i < M; i++) {
  27.         if (degree[i] % 2 == 1) {
  28.             oddCount++;
  29.         }
  30.     }
  31.    
  32.     if (oddCount == 0 || oddCount == 2) {
  33.         cout << "YES" << endl;
  34.     } else {
  35.         cout << "NO" << endl;
  36.     }
  37.    
  38.     // 輸出鄰接矩陣
  39.     for (int i = 0; i < M; i++) {
  40.         for (int j = 0; j < M; j++) {
  41.             cout << adjMatrix[i][j];
  42.             if (j < M - 1) cout << " "; // 確保數字間有空格但行尾無多餘空格
  43.         }
  44.         cout << endl;
  45.     }
  46.    
  47.     return 0;
  48. }
複製代碼
回復 1# may
--------------------------------------------------------
程式說明：
輸入處理

讀取節點數 M 和邊數 N。

建立 M x M 的鄰接矩陣 adjMatrix，並初始化為 0。

建立 degree 陣列，儲存每個節點的度數。

讀取邊資訊

讀取 N 條邊，每條邊 (a, b) 代表 a 和 b 之間有連接。

由於節點編號從 1 開始，因此轉換為 0-based index。

在 adjMatrix 中標記 1 表示有邊，並更新度數 degree[a] 和 degree。

判斷一筆畫條件

計算度數為奇數的節點數 oddCount。

若 oddCount == 0（尤拉迴路）或 oddCount == 2（尤拉路徑），則輸出 "YES"，否則輸出 "NO"。

輸出鄰接矩陣

遍歷 adjMatrix 並輸出矩陣內容，數字間以空格隔開。
------------------------------------------
測資
測資00：Euler 路徑 (符合條件，應輸出 YES)
4 3
1 2
2 3
3 4
預期輸出
YES
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
測資01：Euler 迴路 (所有點度數皆為偶數，應輸出 YES)
4 4
1 2
2 3
3 4
4 1
預期輸出
YES
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
測資 02：無法一筆畫 (奇數度數超過 2 個，應輸出 NO)
5 4
1 2
2 3
3 4
4 5
預期輸出
NO
0 1 0 0 0
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
0 0 0 1 0
測資 03：Euler 迴路 (所有點度數皆為偶數，應輸出 YES)
1 2
2 3
3 1
預期輸出
YES
0 1 1
1 0 1
1 1 0
測資 04：無法一筆畫 (奇數度數超過 2 個，應輸出 NO)
6 5
1 2
2 3
3 4
4 5
5 6
預期輸出
NO
0 1 0 0 0 0
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 0 1 0
0 0 0 1 0 1
0 0 0 0 1 0
這 5 組測資涵蓋 Euler 迴路、Euler 路徑及無法一筆畫的情況
May

TOP

返回列表