#include <iostream> #include <cstring> using namespace std; const int MAXN = 100000; int graph[MAXN][10]; bool visited[MAXN]; int dfs(int v, int max_id) { visited[v] = true; max_id = max(max_id, v); for (int i = 0; i < 10; i++) { int w = graph[v][i]; if (w == -1) break; if (!visited[w]) { max_id = max(max_id, dfs(w, max_id)); } } return max_id; } int main() { int n, m; cin >> n >> m; // 初始化邻接表 memset(graph, -1, sizeof(graph)); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; graph[u-1][i%10] = v-1; } // 对每个点进行DFS for (int i = 0; i < n; i++) { memset(visited, false, sizeof(visited)); int max_id = dfs(i, i); cout << max_id+1 << ' '; } return 0; }这个代码的输出答案全错误,为什么
时间: 2024-01-13 19:04:59 浏览: 23
这段代码的问题在于,每次对一个节点进行DFS时,都会重置visited数组为false,这导致之前已经访问过的节点又被重新访问了,从而导致输出的结果不正确。应该在整个程序的开始就对visited数组进行初始化,而不是在每次DFS之前都进行初始化。修改方式如下:
```
int main() {
int n, m;
cin >> n >> m;
// 初始化邻接表
memset(graph, -1, sizeof(graph));
// 对每个节点进行遍历
memset(visited, false, sizeof(visited));
for (int i = 0; i < n; i++) {
int max_id = dfs(i, i);
cout << max_id+1 << ' ';
}
return 0;
}
```
相关问题
#include <iostream>#include <cstring>#include <queue>using namespace std;const int MAXN = 100000;int graph[MAXN][10];bool visited[MAXN];int bfs(int s) { int max_id = s; queue<int> q; q.push(s); visited[s] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < 10; i++) { int v = graph[u][i]; if (v == -1) break; if (!visited[v]) { visited[v] = true; max_id = max(max_id, v); q.push(v); } } } return max_id;}int main() { int n, m; cin >> n >> m; // 初始化邻接表 memset(graph, -1, sizeof(graph)); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; graph[u-1][i%10] = v-1; } // 对每个节点进行遍历 memset(visited, false, sizeof(visited)); for (int i = 0; i < n; i++) { if (!visited[i]) { int max_id = bfs(i); cout << max_id+1 << ' '; } } return 0;}不使用STL实现这个代码
以下是不使用STL实现该代码的代码实现,主要是手动实现队列和memset函数:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100000;
int graph[MAXN][10];
bool visited[MAXN];
int q[MAXN], front = 0, rear = -1;
void push(int x) {
q[++rear] = x;
}
void pop() {
front++;
}
int front_value() {
return q[front];
}
bool empty() {
return front > rear;
}
void memset_my(bool* arr, bool val, int size) {
for (int i = 0; i < size; i++) {
arr[i] = val;
}
}
int bfs(int s) {
int max_id = s;
push(s);
visited[s] = true;
while (!empty()) {
int u = front_value();
pop();
for (int i = 0; i < 10; i++) {
int v = graph[u][i];
if (v == -1) break;
if (!visited[v]) {
visited[v] = true;
max_id = max(max_id, v);
push(v);
}
}
}
return max_id;
}
int main() {
int n, m;
cin >> n >> m;
// 初始化邻接表
memset(graph, -1, sizeof(graph));
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u-1][i%10] = v-1;
}
// 对每个节点进行遍历
memset_my(visited, false, sizeof(visited));
for (int i = 0; i < n; i++) {
if (!visited[i]) {
int max_id = bfs(i);
cout << max_id+1 << ' ';
}
}
return 0;
}
```
请不使用#include <unordered_map>编译
好的,以下是不使用 `unordered_map` 的实现代码:
```cpp
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 26;
vector<int> graph[MAXN]; // 存储树的关系图
bool visited[MAXN]; // 标记节点是否已经被访问
// 先根遍历函数
void preOrder(int node) {
if (!visited[node]) { // 如果该节点没有被访问
visited[node] = true; // 标记为已访问
cout << char(node + 'A') << " "; // 输出该节点
for (int i = 0; i < graph[node].size(); ++i) { // 遍历该节点的所有子节点
preOrder(graph[node][i]); // 递归遍历子节点
}
}
}
int main() {
char parent, child;
memset(visited, false, sizeof(visited)); // 初始化visited数组
while (cin >> parent >> child) { // 读入树的关系序偶对
graph[parent - 'A'].push_back(child - 'A'); // 添加节点之间的关系
}
for (int i = 0; i < MAXN; ++i) { // 找到根节点
if (graph[i].size() > 0 && !visited[i]) {
preOrder(i); // 从根节点开始先根遍历整棵树
}
}
cout << endl;
return 0;
}
```
这里我们使用一个二维向量 `graph` 存储整棵树的关系图。对于每一对双亲节点和孩子节点的关系,我们都将孩子节点的编号添加到双亲节点的子节点列表中。
同时,我们使用一个布尔数组 `visited` 标记每个节点是否已经被访问。在先根遍历函数 `preOrder` 中,我们从根节点开始遍历整棵树。对于每个节点,我们先判断它是否已经被访问,如果没有被访问,则输出该节点,标记为已访问,并递归遍历该节点的子节点。
最后,在主函数中,我们扫描所有的节点,找到有孩子节点但没有被访问的节点,作为根节点开始先根遍历整棵树。注意,这里我们将节点编号转换成大写字母输出。