数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在给定的非连通图中，执行 Q 次查询后，找到从 K 到 N 的第一个未删除整数
简介
在执行多个查询后，从给定范围内找到分离图中主要的未删除整数，可能是图论中的一个具有挑战性的问题。在本文中，我们研究了识别主要未删除整数的任务，并提供了两种使用 C++ 解决它的方法。每种方法都提供了不同的视角，并使用不同的算法和数据结构。问题包括构建一个图，将某些节点标记为已删除，然后确定指定范围内主要未删除的整数。该图表示节点之间的连接，而已删除的节点是已移除或标记为无效的节点。
方法 1：深度优先搜索 (DFS)
在这种方法中，我们使用图的深度优先搜索遍历。我们从给定节点开始，递归地探索其邻居。我们检查已删除的节点，并继续遍历，直到我们在所需的范围内找到主要未删除的整数。
算法
步骤 1 - 构建图。
步骤 2 - 检查已删除的节点。
步骤 3 - 执行深度优先搜索 (DFS) 算法来遍历图。
步骤 4 - 在 DFS 遍历期间，检查每个节点是否已删除。
步骤 5 - 返回遇到的主要未删除整数。
示例
#include <iostream>
#include <vector>
using namespace std;
vector<bool> traverse;
vector<bool> deleted;
vector<vector<int> > tg;
void dfs(int node, int& result) {
traverse[node] = true;
if (!deleted[node]) {
result = node;
return;
}
for (int i = 0; i < tg[node].size(); i++) {
int neighbor = tg[node][i];
if (!traverse[neighbor]) {
dfs(neighbor, result);
if (result != -1)
return;
}
}
}
int findFirstUndeleted(int K, int N) {
traverse.assign(N + 1, false);
int result = -1;
for (int i = K; i <= N; i++) {
if (!traverse[i]) {
dfs(i, result);
if (result != -1)
return result;
}
}
return result;
}
int main() {
int K = 1;
int N = 10;
// Construct the graph
tg.resize(N + 1);
// Add edges to the graph
// ...
// insert data at the end of the graph
// ...
tg[1].push_back(2);
tg[1].push_back(1);
tg[1].push_back(3);
tg[1].push_back(2);
tg[1].push_back(4);
// Set deleted nodes
deleted.resize(N + 1, false);
deleted[1] = true;
deleted[1] = true;
deleted[1] = true;
int firstUndeleted = findFirstUndeleted(K, N);
cout << "First undeleted integer: " << firstUndeleted << endl;
return 0;
}
输出
First undeleted integer: 2
方法 2：广度优先搜索 (BFS)
在这种方法中，我们使用图的广度优先搜索遍历。我们从给定节点开始，使用队列迭代地探索其邻居。我们标记已删除的节点，并继续遍历，直到我们在所需的范围内找到主要未删除的整数。
算法
步骤 1 - 构建图表。
步骤 2 - 检查已删除的节点。
步骤 3 - 实现广度优先搜索 (BFS) 算法来遍历图表。
步骤 4 - 在 BFS 遍历期间，检查每个节点是否已删除。
步骤 5 - 返回遇到的主要未删除整数。
示例
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<bool> visited;
vector<bool> deleted;
vector<vector<int> > graph;
int findFirstUndeleted(int K, int N) {
visited.assign(N + 1, false);
queue<int> q;
int result = -1;
for (int i = K; i <= N; i++) {
if (!visited[i]) {
q.push(i);
visited[i] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
if (!deleted[node]) {
result = node;
break;
}
for (int j = 0; j < graph[node].size(); j++) {
int neighbor = graph[node][j];
if (!visited[neighbor]) {
q.push(neighbor);
visited[neighbor] = true;
}
}
}
if (result != -1)
break;
}
}
return result;
}
int main() {
int K = 1;
int N = 10;
// Construct the graph
graph.resize(N + 1);
// Add edges to the graph
// ...
// insert nodes
// ...
graph[1].push_back(2);
graph[2].push_back(1);
graph[2].push_back(3);
graph[3].push_back(2);
graph[3].push_back(4);
graph[4].push_back(3);
graph[4].push_back(5);
graph[5].push_back(4);
graph[6].push_back(7);
graph[7].push_back(6);
graph[8].push_back(9);
graph[9].push_back(8);
graph[10].push_back(5);
// Set deleted nodes
deleted.resize(N + 1, false);
deleted[2] = true;
deleted[5] = true;
deleted[7] = true;
int firstUndeleted = findFirstUndeleted(K, N);
cout << "First undeleted integer: " << firstUndeleted << endl;
return 0;
}
输出
First undeleted integer: 1
结论
在本文中，我们研究了两种在分离图的给定范围内查找主要未删除整数的方法。每种方法都提供了独特的视角，并使用了不同的算法和数据结构。方法 1 使用了深度优先搜索 (DFS) 遍历，方法 2 使用了广度优先搜索 (BFS) 遍历。这些方法展示了处理该问题的不同策略，并且根据图的特性和任务的要求，一种方法可能比另一种方法更适用。通过理解这些方法及其在 C++ 中的相应实现，用户可以获得关于有效解决类似基于图的问题的见解。
50 次查看
