이 문제에서는 N개의 노드 그래프가 제공됩니다. 우리의 임무는 수정된 배열의 최소값에서 가능한 최대값을 찾는 것입니다.
그래프의 경우 공통 가장자리를 공유하는 왼쪽에 최소 1개의 노드가 있는 유도 수인 노드의 순열이 있습니다.
문제를 이해하기 위해 예를 들어보겠습니다.
Input : N = 4, edge = {{1, 2}, {2, 3}, {3, 4}, {4, 1}}
Output : 3 솔루션 접근 방식
문제에 대한 간단한 해결책은 한 노드에서 모든 인접 노드를 방문하는 트리를 순회하는 것입니다. 연결된 노드 수의 공식을 사용하여 노드의 순열을 찾습니다.
공식은,
구성요소 크기 - 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