极客笔记C++ 在进行多次查询后，在给定的非连通图中找到从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
方法二：广度优先搜索（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
结论
在本文中，我们研究了从一个断开的图中发现给定运行中的主要未删除数字的两种方法。每种方法都提出了一个独特的视角，并使用了不同的算法和数据结构。方法一使用深度优先搜索（DFS）遍历，方法二使用广度优先搜索（BFS）遍历。这些方法展示了处理问题的不同策略，根据图的特性和任务的要求，一种方法可能比其他方法更合适。通过理解这些方法及其在C ++中的执行，用户可以高效地解决类似的基于图的问题。