Có N người (1..N), muốn chia thành 2 nhóm. Mỗi người ghét một số người khác (dislikes[i]=[a,b] nghĩa a,b không cùng nhóm). Kiểm tra có thể chia không.
Ví dụ: N=4, dislikes=[[1,2],[1,3],[2,4]] → true (nhóm [1,4] và [2,3]).
Giải pháp: kiểm tra đồ thị hai phía (bipartite) bằng DFS tô màu 2 màu.
Xây đồ thị vô hướng từ dislikes
groups[2] lưu người theo màu 0/1
DFS(node, graph, color):
aux = 1-color; nếu groups[aux] có node → false
Thêm node vào groups[color]
Duyệt láng giềng u: nếu groups[aux] chưa có u và DFS(u, aux) false → false
Trả về trueDuyệt 1..N: nếu chưa tô màu, DFS(i, 0), nếu false → false
Trả về true
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: set <int> groups[2]; bool dfs(int node, vector <int> graph[], int x){ int aux = 1 - x; if(groups[aux].count(node)) return false; groups[x].insert(node); for(int u : graph[node]){ if(!groups[aux].count(u) && !dfs(u, graph, aux)) return false; } return true; } bool possibleBipartition(int N, vector<vector<int>>& dislikes) { vector <int> graph[N+1]; for(auto &d : dislikes){ graph[d[0]].push_back(d[1]); graph[d[1]].push_back(d[0]); } for(int i = 1; i <= N; i++) if(!groups[0].count(i) && !groups[1].count(i)) if(!dfs(i, graph, 0)) return false; return true; } }; int main(){ vector<vector<int>> v = {{1,2},{1,3},{2,4}}; Solution ob; cout << ob.possibleBipartition(4, v); }Đầu vào
4 [[1,2],[1,3],[2,4]]
Đầu ra
true