C++でグラフの最大値の順列を見つける

この問題では、N個のノードのグラフが与えられます。私たちのタスクは、変更された配列の最小値の可能な最大値を見つけることです。

グラフの場合、ノードの順列があります。これは、共通のエッジを共有する左側の最小1つのノードを持つ誘導の数です。

問題を理解するために例を見てみましょう

Input : N = 4, edge = {{1, 2}, {2, 3}, {3, 4}, {4, 1}}
Output : 3

ソリューションアプローチ

この問題の簡単な解決策は、1つのノードからツリーをトラバースして、隣接するすべてのノードにアクセスすることです。接続されているノードの数の式を使用して、ノードの順列を見つけます。

式は、

コンポーネントのサイズ-1。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;

int dfs(int x, vector<int> adjMat[], int visited[]){
   int sz = 1;
   visited[x] = 1;
   for (auto ch : adjMat[x])
      if (!visited[ch])
         sz += dfs(ch, adjMat, visited);
   return sz;
}
int maxValPermutationGraph(int n, vector<int> adjMat[]){
   int val = 0;
   int visited[n + 1] = { 0 };
   for (int i = 1; i <= n; i++)
      if (!visited[i])
         val += dfs(i, adjMat, visited) - 1;
   return val;
}
int main(){
   int n = 4;
   vector<int> adjMat[n + 1] = {{1, 2}, {2, 3}, {3, 4}, {4, 1}};
   cout<<"The maximum value permutation of a graph is "<<maxValPermutationGraph(n, adjMat);
   return 0;
}

出力

The maximum value permutation of a graph is 3