列出连通集

#include <iostream>
#include <algorithm> // sort()
#include <vector>
#include <queue>
#define MAXVNUM 10 // 最大点数
using namespace std;

bool visited[MAXVNUM] = {false}; // 以false初始化
vector<int> connected; // 存放连通集
void printConnected() {
    cout << "{ ";
    for( int i = 0; i < connected.size(); i++ )
        cout << connected[i] << " ";
    cout << "}" << endl;
    connected.resize(0); // 清空connected
}

void DFS( vector<int> gragh[], int id ) {
    visited[id] = true; // 标记访问
    connected.push_back(id);
    // 对每一个邻接点
    for( int i = 0; i < gragh[id].size(); i++ )
        if( !visited[ gragh[id][i] ] )
            DFS( gragh, gragh[id][i] );
}
void DFS_Outer( vector<int> gragh[], int N ) {
    // 对每个连通分支
    for( int i = 0; i < N; i++ )
        if( !visited[i] ) {
            DFS( gragh, i );
            printConnected(); // 打印连通分支
        }
}

void BFS( vector<int> gragh[], int N) {
    int id;
    // 对每个连通分支
    for( int i = 0; i < N; i++ )
        if( !visited[i] ) {
            queue<int> Q; // 广度优先
            Q.push(i);
            visited[i] = true;
            while( !Q.empty() ) {
                id = Q.front();
                Q.pop();
                connected.push_back(id);
                // 压入当前结点的所有未访问邻接点
                for( int j = 0; j < gragh[id].size(); j++ )
                    if( !visited[ gragh[id][j] ] ) {
                        Q.push( gragh[id][j] );
                        visited[ gragh[id][j] ] = true;
                    }
            }
            printConnected();
        }
}

int main() {
    int N, E, srcID, dstID; // N:点数 E:边数
    vector<int> gragh[MAXVNUM]; // 起点->[邻点,邻点,...]
    cin >> N >> E;
    for( int i = 0; i < E; i++ ) {
        cin >> srcID >> dstID;
        gragh[srcID].push_back(dstID);
        gragh[dstID].push_back(srcID); // 无向图, 加上反向边
    }
    for( int i = 0; i < N; i++ )
        for( int j = 0; j < gragh[i].size(); j++ )
            sort( gragh[i].begin(), gragh[i].end() ); // 从小到大排序, 因为题目假定每次都从最小编号开始找邻接点

    DFS_Outer( gragh, N );
    // 重置visited
    for( int i =0; i < N; i++ )
        visited[i] = false;
    BFS( gragh, N );
}