題目

水題系列。給出一個圖，求他的連通分量。
科普：連通分量就是一個圖中可以連接最多點的子圖（可以是它本身）的點數量。

輸入

5(點的數量)
1 2(表示1和2連通)
3 4
2 3
0 0(表示停止輸入)

輸出

4

---

解題思路

Er…這道題沒什么難度，反正兩種做法（dfs,bfs）都貼出來。

---

dfs代碼

#include<cstdio> #include<iostream> using namespace std; int walk[101],a[101][101],x,y,maxs,n; int s; int dfs(int x) {s++;//表示搜到的點數加walk[x]=true;//封上for (int i=1;i<=n;i++){if (a[i][x] && !walk[i]){dfs(i);//搜索}} } int main() {scanf("%d",&n);while (true){scanf("%d%d",&x,&y);if (x==0 && y==0) break;a[x][y]=true;a[y][x]=true;}for (int i=1;i<=n;i++)if (!walk[i]) {s=0;dfs(i);maxs=max(maxs,s);}//搜出一個子圖printf("%d",maxs); }

---

bfs代碼(不解釋)

#include<cstdio> #include<iostream> using namespace std; int walk[101],a[101][101],state[101],x,y,maxs,n; int head,tail; int bfs(int x) {state[1]=x;walk[x]=true;head=0;tail=1;do{head++;x=state[head];for (int i=1;i<=n;i++){if (!walk[i] && a[x][i]){tail++;state[tail]=i;walk[i]=true;}}}while (head<tail);maxs=max(maxs,tail); } int main() {scanf("%d",&n);while (true){scanf("%d%d",&x,&y);if (x==0 && y==0) break;a[x][y]=true;a[y][x]=true;}for (int i=1;i<=n;i++)if (!walk[i]) bfs(i);printf("%d",maxs); }

總結

以上是生活随笔為你收集整理的ssl1759-求连通分量【图论，深搜，广搜】的全部內容，希望文章能夠幫你解決所遇到的問題。

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