グラフ内のスーパー頂点を見つけるためのC++プログラム

n個の頂点を持つグラフが与えられたとします。頂点には1からnの番号が付けられ、配列'edges'で指定されたエッジによって接続されます。各頂点には、配列'values'で指定された1からnまでの数値内の'x'値があります。ここで、グラフからスーパー頂点を見つける必要があります。頂点1からiへの最短経路にi番目の頂点と同じ「x」値を持つ頂点がない場合、頂点iは「スーパー頂点」と呼ばれます。この基準を満たすすべての頂点を印刷します。

したがって、入力がn =5のようである場合、値={1、2、2、1、3}、エッジ={{1、2}、{2、3}、{2、3}、{2、4 }、{4、5}}の場合、出力は1 345になります。

頂点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}}

出力

1
3
4
5