Tìm giá trị tối đa của hoán vị đồ thị trong C++

Trong bài toán này, chúng ta được cho một đồ thị N nút. Nhiệm vụ của chúng ta là Tìm giá trị tối đa có thể của giá trị nhỏ nhất của mảng đã sửa đổi.

Đối với đồ thị, ta có một hoán vị các nút là số nút được cảm ứng với ít nhất 1 nút bên trái chia sẻ cạnh chung.

Hãy xem ví dụ sau để hiểu bài toán:

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

Phương pháp giải

Một giải pháp đơn giản là duyệt cây từ một nút thăm tất cả nút lân cận. Ta tìm hoán vị nút bằng công thức số nút kết nối với nó.

Công thức là:

Kích thước thành phần - 1.

Ví dụ

Chương trình minh họa cho giải pháp

#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; }

Kết quả

The maximum value permutation of a graph is 3