題目詳情：
給定一個有 n 個頂點和 m 條邊的無向圖，請用深度優先遍歷（DFS）和廣度優先遍歷（BFS）分別列出其所有的連通集。假設頂點從 0 到 n?1 編號。進行搜索時，假設我們總是從編號最小的頂點出發，按編號遞增的順序訪問鄰接點。
輸入格式:
輸入第 1 行給出 2 個整數 n (0<n≤10) 和 m，分別是圖的頂點數和邊數。隨后 m 行，每行給出一條邊的兩個端點。每行中的數字之間用 1 空格分隔。
輸出格式:
按照"{ v1? v2? ... vk? }"的格式，每行輸出一個連通集。先輸出 DFS 的結果，再輸出 BFS 的結果。
輸入樣例:
8 6
0 7
0 1
2 0
4 1
2 4
3 5
輸出樣例:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }題目解析?
? 逐步分析
? 首先，圖的表示方式。頂點數n不超過10，可以用鄰接表或者鄰接矩陣。因為需要按編號遞增的順序訪問鄰接點，所以鄰接表里的每個頂點的鄰接點應該按升序排列。或者，在每次訪問鄰接點的時候，按從小到大的順序遍歷。例如，對于鄰接矩陣來說，每個頂點x的所有鄰接點，可以按頂點編號從小到大遍歷，即從0到n-1依次檢查是否有邊相連。
? 或者，鄰接表的話，每個頂點的鄰接點列表需要排序。例如，每次添加邊的時候，把鄰接點插入到正確的位置，保持列表的升序。或者，在生成鄰接表之后，對每個頂點的鄰接點列表進行排序。這一步很重要，因為DFS和BFS的遍歷順序必須按照鄰接點的編號遞增的順序進行訪問。所以，圖的存儲結構可能需要鄰接表或者鄰接矩陣，同時要保證遍歷鄰接點的順序是遞增的。
? 例如，鄰接矩陣的話，對于每個頂點，遍歷時檢查所有頂點，按照編號順序依次訪問是否有邊相連。這可能比較方便，特別是當頂點數目較小的時候（n<=10）。這樣，在處理每個頂點的時候，只需要從0到n-1遍歷，檢查是否相連，并且是否未被訪問過。這樣就能保證按照編號遞增的順序訪問鄰接點。
? 那鄰接矩陣可能更適合這個題目，因為處理順序容易控制。比如，假設用鄰接矩陣存儲，那么每個頂點x的鄰接點就是所有y滿足matrix[x][y]為true，并且y按照從小到大排列。所以在遍歷的時候，只需要從0到n-1循環，判斷是否是鄰接點，并且是否已訪問過。
??所以，鄰接矩陣可能更簡單。
? 整個流程應該是這樣的：對于DFS和BFS各需要處理一次：初始化訪問數組，所有頂點未被訪問。然后，按照頂點編號從小到大（從0到n-1）的順序，逐個檢查頂點是否被訪問。如果未被訪問，則從該頂點開始進行DFS或BFS，并將訪問到的頂點記錄下來，形成一個連通集。這樣就能保證每個連通分量都是從其中最小的頂點開始遍歷，并且在遍歷過程中，鄰接點按照編號遞增的順序被訪問。
? 大致步驟如下：
? ? ? 1. 讀取輸入n和m。
? ? ? 2. 構建鄰接矩陣。初始化n×n的二維數組，初始為false。然后讀取m條邊，將對應的兩個頂點之間的邊設為true。
? ? ? 3. 進行DFS遍歷：
? ? ? ? ? ? ? a. 初始化一個訪問數組visited，所有元素初始為false。
? ? ? ? ? ? ? b. 按照頂點編號從小到大遍歷每個頂點i：
? ? ? ? ? ? ? ? ? ? ?i. 如果未被訪問，則開始DFS遍歷，并將結果記錄為一個連通集。
? ? ? ? ? ? ? ? ? ? ii. 在DFS過程中，將訪問的頂點按順序保存，并在結束后輸出。
? ? ? 4. 進行BFS遍歷，同樣的邏輯，但使用隊列。
? 推薦代碼
??
#include <iostream>
#include <vector>
#include <queue>
using namespace std;void DFS(int v, vector<bool>& visited, const vector<vector<bool>>& adj, vector<int>& component) {visited[v] = true;component.push_back(v);for (int i = 0; i < adj.size(); ++i) {if (adj[v][i] && !visited[i]) {DFS(i, visited, adj, component);}}
}void BFS(int v, vector<bool>& visited, const vector<vector<bool>>& adj, vector<int>& component) {queue<int> q;q.push(v);visited[v] = true;component.push_back(v);while (!q.empty()) {int current = q.front();q.pop();for (int i = 0; i < adj.size(); ++i) {if (adj[current][i] && !visited[i]) {visited[i] = true;component.push_back(i);q.push(i);}}}
}int main() {int n, m;cin >> n >> m;vector<vector<bool>> adj(n, vector<bool>(n, false));for (int i = 0; i < m; ++i) {int u, v;cin >> u >> v;adj[u][v] = true;adj[v][u] = true;}// DFSvector<bool> visited(n, false);for (int i = 0; i < n; ++i) {if (!visited[i]) {vector<int> component;DFS(i, visited, adj, component);cout << "{ ";for (int v : component) {cout << v << " ";}cout << "}" << endl;}}// BFSvisited.assign(n, false);for (int i = 0; i < n; ++i) {if (!visited[i]) {vector<int> component;BFS(i, visited, adj, component);cout << "{ ";for (int v : component) {cout << v << " ";}cout << "}" << endl;}}return 0;
}自我實現代碼?
??
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>using namespace std;int n,m;
int g[15][15];
int vis[15];
vector<int>res;
queue<int>q;void dfs(int x)
{res.push_back(x);vis[x]=1;for(int i=1;i<=n;++i){if(g[x][i]==1&&!vis[i]){vis[i]=1;dfs(i);}}
}void bfs(int x)
{res.push_back(x);q.push(x);vis[x]=1;while(!q.empty()){int xx=q.front();q.pop();for(int i=1;i<=n;++i){if(g[xx][i]==1&&!vis[i]){res.push_back(i);vis[i]=1;q.push(i);}}}}int main()
{cin>>n>>m;int a,b;for(int i=1;i<=m;++i){cin>>a>>b;g[a+1][b+1]=1;g[b+1][a+1]=1; }for(int i=1;i<=n;++i){if(!vis[i]){res.clear();dfs(i);cout<<"{";for(int i=0;i<res.size();++i){cout<<" "<<res[i]-1;}cout<<" }"<<endl;}}memset(vis,0,sizeof(vis));for(int i=1;i<=n;++i){if(!vis[i]){while(!q.empty())q.pop();res.clear();bfs(i);cout<<"{";for(int i=0;i<res.size();++i){cout<<" "<<res[i]-1;}cout<<" }"<<endl;}}return 0;
}
