Possible Bipartition ใน C++

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

มี N คน ต้องการแบ่งเป็น 2 กลุ่ม โดยมีคู่ที่เกลียดกัน (dislikes[i]=[a,b]) ไม่อนุญาตให้อยู่กลุ่มเดียวกัน ต้องการทราบว่าแบ่งได้หรือไม่

ตัวอย่าง: N=4, dislikes=[[1,2],[1,3],[2,4]] → true (กลุ่ม [1,4] และ [2,3])

วิธีแก้ปัญหา (Graph Bipartite Check - DFS)

1. สร้างกราฟ adjacency list จาก dislikes
2. ใช้ DFS 2-coloring: พยายามระบายสี 2 สี (0,1) ให้เพื่อนบ้านต่างสี
3. ถ้าพบขัดแย้ง (เพื่อนบ้านมีสีเดียวกัน) → false
4. ตรวจสอบทุก connected component

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

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

class Solution {
public:
    vector<int> color;
    vector<vector<int>> graph;
    
    bool dfs(int node, int c) {
        color[node] = c;
        for(int nei : graph[node]) {
            if(color[nei] == -1) {
                if(!dfs(nei, 1-c)) return false;
            } else if(color[nei] == c) {
                return false;
            }
        }
        return true;
    }
    
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        graph.assign(N+1, {});
        for(auto& d : dislikes) {
            graph[d[0]].push_back(d[1]);
            graph[d[1]].push_back(d[0]);
        }
        
        color.assign(N+1, -1);
        for(int i = 1; i <= N; i++) {
            if(color[i] == -1) {
                if(!dfs(i, 0)) return false;
            }
        }
        return true;
    }
};

int main() {
    vector<vector<int>> v = {{1,2},{1,3},{2,4}};
    Solution ob;
    cout << (ob.possibleBipartition(4, v) ? "true" : "false");
    return 0;
}

อินพุต

4 [[1,2],[1,3],[2,4]]

เอาต์พุต

true