ในปัญหานี้ เราได้รับกราฟของโหนด 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
