在不使用#include <unordered_set>这条头文件的情况下修改代码,使其可以通过oj
时间: 2024-09-18 09:10:08 浏览: 37
unordered_map和unordered_set的模拟实现
5星 · 资源好评率100%
如果要在不使用 `#include <unordered_set>` 的情况下实现类似功能,我们可以使用数组或列表来模拟邻接表,并使用位运算来标记已访问的箱子。这里是一个基于数组的解决方案:
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 100; // 假设箱子不超过100个
// 用一个布尔数组表示箱子是否被访问过,初始化全为false
bool visited[MAX_N + 1];
// 定义邻接矩阵,使用二维数组表示箱子之间的钥匙关系
vector<vector<int>> graph(MAX_N + 1, vector<int>(MAX_N + 1));
void findUnlockable(int n, vector<int>& graph, vector<int>& result) {
// 初始化遍历标志
for (int i = 0; i <= n; ++i) {
visited[i] = false;
}
// 从第一个箱子开始,进行深度优先搜索
dfs(1, graph, result);
}
void dfs(int node, vector<int>& graph, vector<int>& result) {
// 标记当前箱子已访问
visited[node] = true;
// 添加当前箱子到结果中
result.push_back(node);
// 遍历邻居节点
for (int nei : graph[node]) {
// 如果邻居未被访问,则递归继续搜索
if (!visited[nei]) {
dfs(nei, graph, result);
}
}
}
int main() {
int n, m;
cin >> n >> m;
// 读取钥匙隐藏关系并更新邻接矩阵
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
graph[u][v] = 1; // 表示箱子u的钥匙在箱子v中,这里的1只是一个标记
}
vector<int> unlockable; // 用于存储结果
findUnlockable(n, graph, unlockable);
// 输出结果
for (int box : unlockable) {
cout << box << " ";
}
cout << endl;
return 0;
}
```
请注意,这种方法仅适用于箱子数量较小的情况,因为数组大小是固定的,不适合大规模的数据。如果输入规模未知或者可能会很大,建议还是使用 `unordered_set` 或其他哈希集合来优化查找效率。
阅读全文