https://pta.patest.cn/pta/test/558/exam/4/question/9495
解說(shuō)
這題沒(méi)什么難度审轮，只要對(duì)BFS和DFS算法中的訪問(wèn)代碼稍作修改即可。另外需要特別注意的是，執(zhí)行完一次遍歷之后，需要把visited數(shù)組中的記錄重置一次，不然第二次遍歷沒(méi)法進(jìn)行。
代碼
#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;
}
