列出连通集

https://pta.patest.cn/pta/test/558/exam/4/question/9495

解说

这题没什么难度，只要对BFS和DFS算法中的访问代码稍作修改即可。另外需要特别注意的是，执行完一次遍历之后，需要把visited数组中的记录重置一次，不然第二次遍历没法进行。

代码

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
class Graph {
private:
    int n;
    bool *visited;
    vector<int> *edges;
public:
    Graph(int N) {
        n = N;
        visited = new bool[N];
        edges = new vector<int>[N];
        memset(visited, 0, N);
    }
    ~Graph() {
        delete[] visited;
        delete[] edges;
    }
    void insert(int a, int b) {
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    void DFS(int n) {
        cout << n << " ";
        visited[n] = true;
        sort(edges[n].begin(), edges[n].end());
        for (int vertex:edges[n])
        {
            if (!visited[vertex])
            {
                DFS(vertex);
            }
        }
    }
    void DFSprint(int n) {
        cout << "{ ";
        DFS(n);
        cout << "}" << endl;
    }
    void DFSsearch() {
        
        DFSprint(0);
        for (int i = 0; i <n ; i++)
        {
            if (!visited[i])
            {
                DFSprint(i);
            }
        }
    }
    void BFSprint(int n) {
        cout << "{ ";
        BFS(n);
        cout << "}" << endl;
    }
    void BFSsearch() {
        BFSprint(0);
        for (int i = 0; i <n; i++)
        {
            if (!visited[i])
            {
                BFSprint(i);
            }
        }
    }
    void visit_reset() {
        memset(visited, 0, n);
    }
    void BFS(int n) {
        queue<int>q;
        q.push(n);
        while (!q.empty())
        {
            int vertex = q.front();
            q.pop();
            cout << vertex << " ";
            visited[vertex] = true;
            sort(edges[vertex].begin(), edges[vertex].end());
            for (int v:edges[vertex])
            {
                if (!visited[v])
                {
                    visited[v] = true;
                    q.push(v);
                }       
            }
        }
    }
};

int main()
{
    int N, M;
    cin >> N >> M;
    Graph graph(N);
    int x, y;
    for (int i = 0; i < M; i++)
    {
        cin >> x >> y;
        graph.insert(x, y);
    }
    graph.DFSsearch();
    graph.visit_reset();
    graph.BFSsearch();
    return 0;
}