Trong bài toán này, chúng ta được đưa ra một đồ thị gồm N nút. Nhiệm vụ của chúng ta là Tìm giá trị lớn nhất có thể của giá trị nhỏ nhất của mảng đã sửa đổi.
Đối với biểu đồ, chúng ta có một hoán vị của các nút là số lần cảm ứng với tối thiểu 1 nút ở bên trái của nó có chung một cạnh.
Hãy lấy một ví dụ để hiểu vấn đề,
Input : N = 4, edge = {{1, 2}, {2, 3}, {3, 4}, {4, 1}}
Output : 3 Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là duyệt cây từ một nút đến thăm tất cả các nút lân cận của nó. Chúng tôi sẽ tìm hoán vị của các nút bằng cách sử dụng công thức về số nút được kết nối với nó.
Công thức là,
Kích thước của thành phần - 1.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The maximum value permutation of a graph is 3