f668 - FJCU_109_Winter_Day1_Lab3 Adjacency Matrix 和 Adjacency List 練習
題目描述
題目給定一個無向簡單圖的點數 N 和邊數 M，以及每條邊的兩個端點。要求輸出每個點的相鄰點列表，相鄰點按照點的編號升序排列。
解題思路
本題可以使用鄰接矩陣來表示圖。鄰接矩陣是一個 N x N 的二維陣列，其中 a[i][j] = 1 表示點 i 和點 j 之間存在邊，a[i][j] = 0 表示不存在邊。
首先，初始化鄰接矩陣，將對角線元素設為 1，表示每個點與自身相鄰。然後，遍歷輸入的每條邊，將對應的鄰接矩陣元素設為 1。最後，遍歷每個點，輸出其相鄰點的列表。
複雜度分析
- 時間複雜度: O(N^2 + M)
- 空間複雜度: O(N^2)
程式碼
#include <iostream>
using namespace std;
int a[11][11],n,m,x,y;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=1;i<=n;++i){
a[i][i]=1;
}
while(m--){
cin >> x >> y;
a[x][y]=1;
a[y][x]=1;
}
for(int i=1;i<=n;++i){
cout << i << ": ";
for(int j=1;j<=n;++j){
if(i!=j&&a[i][j]){
cout << j << " ";
}
}
cout << "\n";
}
}