หาค่าสูงสุดของ Permutation ของกราฟใน C++

ในปัญหานี้ เราได้รับกราฟที่มี N โหนด งานของเราคือ การหาค่าสูงสุดที่เป็นไปได้ของค่าต่ำสุดของอาร์เรย์ที่ปรับเปลี่ยนแล้ว

สำหรับกราฟ เรามี permutation ของโหนดซึ่งเป็นจำนวน induced subgraphs ที่มีอย่างน้อย 1 โหนดทางด้านซ้ายที่มีขอบร่วมกัน

ตัวอย่างเพื่อความเข้าใจ

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

แนวทางแก้ปัญหา

วิธีแก้ที่ง่ายคือการเดินผ่านกราฟจากโหนดหนึ่งไปเยี่ยมโหนดติดกันทั้งหมด เราจะหา permutation ของโหนดโดยใช้สูตรจำนวนโหนดที่เชื่อมต่อกับมัน

สูตรคือ:

ขนาดของ connected component - 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];
    adjMat[1].push_back(2);
    adjMat[2].push_back(1);
    adjMat[2].push_back(3);
    adjMat[3].push_back(2);
    adjMat[3].push_back(4);
    adjMat[4].push_back(3);
    adjMat[4].push_back(1);
    adjMat[1].push_back(4);
    
    cout << "The maximum value permutation of a graph is " << maxValPermutationGraph(n, adjMat);
    return 0;
}

ผลลัพธ์

The maximum value permutation of a graph is 3