|
886. 可能的二分法
题目：
给定一组?n?人（编号为?1, 2, ..., n），?我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。
给定整数 n?和数组 dislikes?，其中?dislikes[i] = [ai, bi]?，表示不允许将编号为 ai?和??bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。
示例 1：
输入：n = 4, dislikes = [[1,2],[1,3],[2,4]]
输出：true
解释：group1 [1,4], group2 [2,3]
示例 2：
输入：n = 3, dislikes = [[1,2],[1,3],[2,3]]
输出：false
示例 3：
输入：n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出：false
提示：
1 <= n <= 2000
0 <= dislikes.length <= 104
dislikes[i].length == 2
1 <= dislikes[i][j] <= n
ai?< bi
dislikes?中每一组都 不同
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/possible-bipartition
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
用两种颜色给图着色，能着色成功则可以把N个人分为两个小组，否则不能。
首先，我们利用一个容器来存储不喜欢的人的元素，从而构成一个二重的表。
其次，我们利用DFS的方式（也可以是BFS），来判断是否存在两两匹配的情况。
最后，如果中间出现无法匹配的情况，则直接返回false，否则，返回true。
代码：
class Solution {
public:
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
vector<int> colors(N + 1,0);
vector<unordered_set<int>> graph(N+1);
for(const auto& dislike : dislikes)
{
graph[dislike[0]].insert(dislike[1]);
graph[dislike[1]].insert(dislike[0]);
}
for(int i = 1;i <= N;i++)
{
if(!colors[i] && ! dfs(N,graph,i,1,colors))
return false;
}
return true;
}
private:
bool dfs(int& N,vector<unordered_set<int>>& graph,int i,int color,vector<int>& colors)
{
if(colors[i] != 0)
return colors[i] == color;
colors[i] = color;
for(const auto& neighbor : graph[i])
{
if(!dfs(N,graph,neighbor,-1*color,colors))
return false;
}
return true;
}
};
|