二分法模板题,每日打卡10.16
class Solution {
public:
vector<vector<int>> g;
vector<int> color;
bool dfs(int u, int c)
{
color[u] = c;
for (auto v : g[u])
{
if (color[v]) {
if (color[v] == c) return false; // 颜色矛盾
}
else if (!dfs(v, 3 - c)) return false;//邻接点没有颜色,染色,如果矛盾返回false
}
return true;//该连通块没有矛盾
}
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
g.resize(n);
color.resize(n);
for (auto& e : dislikes)
{
int a = e[0] - 1, b = e[1] - 1;
g[a].push_back(b), g[b].push_back(a);//邻接表
}
for (int i = 0; i < n; i ++)
if (!color[i] && !dfs(i, 2))// 如果没染色,染色后有矛盾,则不能二分
return false;
return true;
}
};
标签:return,886,color,dfs,二分法,int,false,LeetCode
From: https://www.cnblogs.com/zjy0/p/16798908.html