f670 - FJCU_109_Winter_Day1_Lab5 連通塊數量
題目描述
題目給定一個無向圖，要求計算圖中連通塊的數量。圖由 N 個節點和 M 條邊組成，節點編號從 1 到 N。
解題思路
本題可以使用深度優先搜尋 (DFS) 來解決。主要思路是遍歷圖中的每個節點，如果該節點尚未被訪問過，則從該節點開始進行 DFS，將所有與該節點連通的節點標記為已訪問。每次成功執行一次 DFS，連通塊的數量就加一。
具體步驟如下：
- 初始化一個二維陣列
a作為鄰接矩陣，表示圖的連接關係。 - 讀取輸入，建立鄰接矩陣。
- 遍歷所有節點，如果節點尚未被訪問過，則調用 DFS 函數。
- 在 DFS 函數中，將當前節點標記為已訪問，然後遞歸地訪問與當前節點相鄰的所有未訪問節點。
- 每次成功執行一次 DFS，連通塊的數量加一。
- 輸出連通塊的數量。
複雜度分析
- 時間複雜度: O(N^2)，其中 N 是節點的數量。因為鄰接矩陣的遍歷需要 O(N^2) 的時間，DFS 最多訪問所有節點和邊，時間複雜度為 O(N + M)，但因為 M 最大為 N(N-1)/2，所以整體時間複雜度為 O(N^2)。
- 空間複雜度: O(N^2)，主要用於儲存鄰接矩陣。DFS 的遞迴深度最壞情況下為 N，因此遞迴堆疊的空間複雜度為 O(N)。總空間複雜度為 O(N^2)。
程式碼
#include <stdio.h>
char a[11][11],n,m,x,y,ans;
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[3],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
inline void dfs(char xx,char yy){
a[xx][yy]=0;
for(int i=1;i<=n;++i){
if(a[xx][i])
dfs(xx,i);
if(a[i][yy])
dfs(i,yy);
}
}
int main(){
n=read();
m=read();
for(int i=1;i<=n;++i)
a[i][i]=1;
while(m--){
x=read();
y=read();
a[x][y]=1;
a[y][x]=1;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(a[i][j]){
dfs(i,j);
++ans;
}
write(ans);
}