โปรแกรม C++ นับจำนวนชุดสูงสุดแบ่งโหนดกราฟที่ขอบเชื่อมชุดติดกัน

คำอธิบายปัญหา

สมมติว่าเรามีเมทริกซ์สมัยติดกันของกราฟ G ต้องการตรวจสอบว่าแบ่งโหนดเป็นชุดไม่ว่าง V1...Vk ได้ไหม ที่ทุกขอบเชื่อมโหนดจาก 2 ชุดที่ติดกัน ถ้าทำได้ ต้องการค่า k สูงสุด

ตัวอย่าง: เมทริกซ์ 6x6 ตามตาราง ผลลัพธ์คือ 4

ขั้นตอนการแก้ปัญหา

กำหนดอาร์เรย์ dp ขนาด 210
n := ขนาดเมทริกซ์
fl := 1, ans := 0
สำหรับ i := 0 ถึง n-1 และ fl ไม่เป็นศูนย์:
    เติม dp ด้วย -1
    dp[i] := 0
    คิว q ใส่ i
    while q ไม่ว่าง:
        x := ตัวหน้าของ q
        ลบตัวหน้าออกจาก q
        สำหรับ j := 0 ถึง n-1:
            ถ้า matrix[x,j] == 1:
                ถ้า dp[j] == -1:
                    dp[j] := dp[x] + 1
                    ใส่ j ลง q
                มิฉะนั้นถ้า |dp[j] - dp[x]| != 1:
                    fl := 0
    สำหรับ j := 0 ถึง n-1: ans := max(ans, dp[j])
ถ้า fl == 0: คืนค่า -1
มิฉะนั้น: คืนค่า ans + 1

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int solve(vector<vector<int>> matrix){
    int dp[210];
    int n = matrix.size();
    int fl = 1;
    int ans = 0;
    for (int i = 0; i < n && fl; i++){
        memset(dp, -1, sizeof(dp));
        dp[i] = 0;
        queue<int> q;
        q.push(i);
        while (!q.empty()){
            int x = q.front();
            q.pop();
            for (int j = 0; j < n; j++){
                if (matrix[x][j] == 1){
                    if (dp[j] == -1){
                        dp[j] = dp[x] + 1;
                        q.push(j);
                    } else if (abs(dp[j] - dp[x]) != 1)
                        fl = 0;
                }
            }
        }
        for (int j = 0; j < n; j++) ans = max(ans, dp[j]);
    }
    if (fl == 0) return -1;
    else return ans + 1;
}

int main(){
    vector<vector<int>> matrix = { { 0, 1, 0, 1, 1, 0 },
                                     { 1, 0, 1, 0, 0, 1 },
                                     { 0, 1, 0, 1, 0, 0 },
                                     { 1, 0, 1, 0, 0, 0 },
                                     { 1, 0, 0, 0, 0, 0 },
                                     { 0, 1, 0, 0, 0, 0 } };
    cout << solve(matrix) << endl;
}

อินพุต

{ { 0, 1, 0, 1, 1, 0 }, { 1, 0, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0 }, { 1, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0, 0 } }

เอาต์พุต

4