C++程序找出图中的超级顶点
假设给定一个有 n 个顶点的图。顶点编号为 1 到 n，它们由数组“edges”中给定的边连接。每个顶点都有一个从 1 到 n 的数字内的“x”值，该数字在数组“values”中给出。现在，我们必须从图中找出超顶点。当从顶点 1 到 i 的最短路径没有与第 i 个顶点具有相同“x”值的顶点时，顶点 i 被称为“超级顶点”。我们打印出所有满足这个标准的顶点。
所以，如果输入像 n = 5，values = {1, 2, 2, 1, 3}，edges = {{1, 2}, {2, 3}, {2, 3}, {2, 4 }, {4, 5}}，则输出将为 1 3 4 5。
除顶点 2 之外的每个顶点都满足标准。因此，顶点 2 被排除在外。
脚步
为了解决这个问题，我们将遵循以下步骤 -
Define arrays vertexVal, frq, and chk of size: 100005.Define an array vcti of size 200005.
Define a function dfs(), this will take j, k,
if frq[vertexVal[j]] is same as 0, then:
chk[j] := 1
(increase frq[vertexVal[j]] by 1)
for each value a in vcti[j], do:
if a is not equal to k, then:
dfs(a, j)
(decrease frq[vertexVal[j]] by 1)
for initialize i := 0, when i < n, update (increase i by 1), do:
vertexVal[i] := values[i]
for initialize i := 0, when i < n, update (increase i by 1), do:
a := first value of edges[i]
b := second value of edges[i]
insert b at the end of vcti[a]
insert a at the end of vcti[b]
dfs(1, 0)
for initialize i := 1, when i <= n, update (increase i by 1), do:
if chk[i] is non-zero, then:
print(i)
示例
让我们看看以下实现以更好地理解 -
#include <bits/stdc++.h>using namespace std;
int n;
int vertexVal[100005], frq[100005], chk[100005];
vector<int> vcti[200005];
void dfs(int j, int k){
if (frq[vertexVal[j]] == 0)
chk[j] = 1;
frq[vertexVal[j]]++;
for (auto a : vcti[j]) {
if (a != k)
dfs(a, j);
}
frq[vertexVal[j]]--;
}
void solve(int values[], vector<pair<int, int>> edges){
for (int i = 0; i < n; i++)
vertexVal[i] = values[i];
for (int i = 0; i < n; i++){
int a, b;
a = edges[i].first;
b = edges[i].second;
vcti[a].push_back(b);
vcti[b].push_back(a);
}
dfs(1, 0);
for (int i = 1;i <= n; i++){
if (chk[i]) cout<< i <<endl;
}
}
int main() {
n = 5;
int values[] = {1, 2, 2, 1, 3}; vector<pair<int, int>> edges = {{1, 2}, {2, 3}, {2, 3}, {2, 4}, {4, 5}};
solve(values, edges);
return 0;
}
输入
5, {1, 2, 2, 1, 3}, {{1, 2}, {2, 3}, {2, 3}, {2, 4}, {4, 5}}输出结果13
4
5
以上是 C++程序找出图中的超级顶点 的全部内容， 来源链接： utcz.com/z/363479.html
