Open azl397985856 opened 2 years ago
Graph + DFS
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
G = collections.defaultdict(list)
for f, t in dislikes:
G[f].append(t)
G[t].append(f)
Groups = {}
def dfs(root, label):
Groups[root] = label
for nei in G[root]:
if nei in Groups and Groups[nei] == label:
return False
elif nei not in Groups and not dfs(nei, -label):
return False
return True
for i in range(1, n+1):
if i not in Groups and not dfs(i, 1):
return False
return True
Time: O(V+E) Space: O(V^2)
染色法
class Solution {
private:
vector<int> colors;
vector<vector<int>> graph;
bool dfs(int v, int color) {
colors[v] = color;
for (int u : graph[v]) {
if (colors[u]) {
if (colors[u] == color) return false;
} else if (!dfs(u, color ^ 1)) {
return false;
}
}
return true;
}
public:
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
colors.resize(n + 1);
graph.resize(n + 1);
for (auto dislike : dislikes) {
graph[dislike[0]].push_back(dislike[1]);
graph[dislike[1]].push_back(dislike[0]);
}
for (int i = 1; i <= n; i++) {
if (!colors[i] && !dfs(i, 0)) return false;
}
return true;
}
};
O(m+n) O(n)
图+DFS
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
Graph = collections.defaultdict(list)
for u,v in dislikes:
Graph[u].append(v)
Graph[v].append(u)
dict = {}
def dfs(node,c=0):
if node in dict:
return dict[node] == c
dict[node] = c
for nei in Graph[node]:
if not dfs(nei,c^1):
return False
return True
for i in range(1,n+1):
if i not in dict:
if not dfs(i):
return False
return True
二分图。首先构造图,深度遍历图,遍历的过程中给顶点涂色,相邻顶点需要涂不一样的颜色。如果这个逻辑能够一直进行下去,则返回true,中间发生冲突,则返回false。
class Solution {
List<Integer>[] graph;
int[] colors;
public boolean possibleBipartition(int n, int[][] dislikes) {
graph = new ArrayList[n + 1];
colors = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
graph[i] = new ArrayList<>();
}
for (int[] d : dislikes) {
int a = d[0];
int b = d[1];
graph[a].add(b);
graph[b].add(a);
}
for (int i = 1; i <= n; i++) {
if (colors[i] == 0) {
if (!dfs(i, 1))
return false;
}
}
return true;
}
boolean dfs(int x, int c) {
if (colors[x] != 0) {
return colors[x] == c;
}
colors[x] = c;
for (int i = 0; i < graph[x].size(); i++) {
int next = graph[x].get(i);
if (!dfs(next, -c)) {
return false;
}
}
return true;
}
}
以邻接矩阵创建无向图,遍历顶点着色同时深度遍历其相邻顶点着反色,若发现相邻将要着色的顶点已经着色并且和期望色不同则返回false,成功着色返回true
class Solution {
List<Integer>[] graph;
int[] color;
public boolean possibleBipartition(int n, int[][] dislikes) {
graph = new ArrayList[n + 1];
color = new int[n + 1];
for (int node = 1; node <= n; node++) {
graph[node] = new ArrayList<>();
}
for (int[] edge : dislikes) {
graph[edge[0]].add(edge[1]);
graph[edge[1]].add(edge[0]);
}
for (int node = 1; node <= n; node++) {
if (color[node] == 0 && !dfs(node, 1)) {
return false;
}
}
return true;
}
boolean dfs(int node, int c) {
if (color[node] != 0) {
return color[node] == c;
}
color[node] = c;
for (int nei : graph[node]) {
if (!dfs(nei, -c)) {
return false;
}
}
return true;
}
}
class Solution {
public boolean possibleBipartition(int N, int[][] dislikes) {
int[][] graph = new int[N][N];
for (int[] d : dislikes) {
graph[d[0] - 1][d[1] - 1] = 1;
graph[d[1] - 1][d[0] - 1] = 1;
}
int[] group = new int[N];
for (int i = 0; i < N; i++) {
if (group[i] == 0 && !dfs(graph, group, i, 1)) {
return false;
}
}
return true;
}
private boolean dfs(int[][] graph, int[] group, int index, int g) {
group[index] = g;
for (int i = 0; i < graph.length; i++) {
if (graph[index][i] == 1) {
if (group[i] == g) {
return false;
}
if (group[i] == 0 && !dfs(graph, group, i, -g)) {
return false;
}
}
}
return true;
}
}
思路:染色法二分无向图,学习了 代码:
vector<int> colors;
vector<vector<int>> G;
bool possibleBipartition(int n, vector<vector<int>>& dislikes)
{
G=vector<vector<int>>(n);
for(auto& d:dislikes)
{
G[d[0]-1].push_back(d[1]-1);
G[d[1]-1].push_back(d[0]-1);
}
colors=vector<int>(n,0);
for(int i=0;i<colors.size();i++)
{
if(colors[i]==0 && !dfs(i,1))
return false;
}
return true;
}
bool dfs(int cur, int color)
{
colors[cur]=color;
for(int next:G[cur])
{
if(colors[next]==color)
return false;
if(colors[next]==0 && !dfs(next,-color))
return false;
}
return true;
}
复杂度: 时间复杂度:O(V+E) 空间复杂度:O(V+E)
非常类似于上色graph 使之成为bipartite graph. 第一个dislike 的两个人进去不同颜色圈。 如果后面的某个人又在红色圈,又在蓝色圈,无法成为bipartite graph。 如果成功分成two set of different colors, 那么代表分类成功了。
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
graph = collections.defaultdict(list)
for di, dj in dislikes:
graph[di-1].append(dj-1)
graph[dj-1].append(di-1)
colors = [0] * n
for i in range(len(graph)):
if colors[i] != 0: continue # visited
queue = collections.deque()
queue.append(i)
colors[i] = 1
while queue:
person = queue.popleft()
for p in graph[person]:
if colors[p] == 0:
colors[p] = -colors[person]
# bipartite 只有两个色, dislike 就把p 放在 另一个 set
queue.append(p)
elif colors[p] == colors[person]:
return False
return True
time complexity: O(V+E) space complexity: O(V+E)
class Solution(object):
def possibleBipartition(self, n, dislikes):
"""
:type n: int
:type dislikes: List[List[int]]
:rtype: bool
"""
graph = [[0] * n for i in range(n)]
colors = [0] * n
for a, b in dislikes:
graph[a - 1][b - 1] = 1
graph[b - 1][a - 1] = 1
for i in range(n):
if colors[i] == 0 and not self.dfs(graph, colors, i, 1, n):
return False
return True
def dfs(self, graph, colors, i, color, n):
colors[i] = color
for j in range(n):
# dislike eachother
if graph[i][j] == 1:
if colors[j] == color:
return False
if colors[j] == 0 and not self.dfs(graph, colors, j, -1 * color, n):
return False
return True
class Solution:
def dfs(self, g, colors, n, i, c):
"""
g: graph
colors: color list
n: # of v
i: v
c: group, -1 or 1
"""
# we color i as c
colors[i] = c
# for every dislikes, we try to assign -c, if success, then we can assign c to current v, else false
for j in range(n):
# for each dislike v, we color -c
if g[i][j] != 0:
# if disliked v has already been colored as same color c, then failed
if colors[j] == c:
return False
# if disliked v has not been colored, then we try to color it as -c, if success, continue to color the next
# dislike v, else False
if colors[j] == 0 and not self.dfs(g, colors, n, j, -1*c):
return False
return True
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
# create a graph
g = [[0]*n for _ in range(n)]
for i, j in dislikes:
g[i-1][j-1] = 1
g[j-1][i-1] = 1
# create colors, -1 group1, 1 group2
colors = [0]*n
for i in range(n):
# if not colored, we assign it 1
if colors[i] == 0 and not self.dfs(g, colors, n, i, 1):
return False
return True
class Solution:
def dfs(self, graph, colors, i, color, N):
colors[i] = color
for j in range(N):
# dislike eachother
if graph[i][j] == 1:
if colors[j] == color:
return False
if colors[j] == 0 and not self.dfs(graph, colors, j, -1 * color, N):
return False
return True
def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
graph = [[0] * N for i in range(N)]
colors = [0] * N
for a, b in dislikes:
graph[a - 1][b - 1] = 1
graph[b - 1][a - 1] = 1
for i in range(N):
if colors[i] == 0 and not self.dfs(graph, colors, i, 1, N):
return False
return True
Build graph, color node, dfs Use an array of list to build graph of dislike Use map to store color of each node Set a node with color 0, then the enemy of it should set to color 1 DFS set color and check if node has right color
class Solution {
List<Integer>[] graph;
Map<Integer, Integer> colorMap;
public boolean possibleBipartition(int n, int[][] dislikes) {
colorMap = new HashMap<>();
graph = new ArrayList[n+1];
for (int i = 0; i <= n; i++) { // initialize graph
graph[i] = new ArrayList<>();
}
for (int[] dk : dislikes) { // build graph
graph[dk[0]].add(dk[1]);
graph[dk[1]].add(dk[0]);
}
for (int node = 1; node <= n; node++) {
if (!colorMap.containsKey(node)) { // no color
boolean possible = dfs(node, 0); // check p
if (possible == false) { // check bipartition possible
return false;
}
}
else {
continue;
}
}
return true;
}
public boolean dfs(int node, int c) {
if (colorMap.containsKey(node)) { // has color
return colorMap.get(node) == c; // check color
}
colorMap.put(node, c); // color it
for (int notFriend : graph[node]) { // traverse its enemy
boolean check = dfs(notFriend, c^1); // check enemy
if (check == false) {
return false;
}
}
return true;
}
}
Time:O(V+E) Space:O(V+E)
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
self.graph = [[] for _ in range(n)]
for i in range(len(dislikes)):
self.graph[dislikes[i][0]-1].append(dislikes[i][1]-1)
self.graph[dislikes[i][1]-1].append(dislikes[i][0]-1)
self.visited = [False for _ in range(n)]
self.color = [False for _ in range(n)]
self.res = True
for i in range(n):
if self.visited[i] is False:
self.dfs(i)
return self.res
def dfs(self, node):
if self.res is False:
return
self.visited[node] = True
for i in self.graph[node]:
if self.visited[i]:
if self.color[i] == self.color[node]:
self.res = False
return
else:
self.color[i] = not self.color[node]
self.dfs(i)
https://leetcode-cn.com/problems/possible-bipartition/
给定一组 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 中每一组都 不同
不喜欢做图
JavaScript Code:
/**
* @param {number} n
* @param {number[][]} dislikes
* @return {boolean}
*/
var possibleBipartition = function(N, dislikes) {
let graph = [...Array(N + 1)].map(() => Array()), // 动态创建二维数组
colors = Array(N + 1).fill(-1);
// build the undirected graph
for (const d of dislikes) {
graph[d[0]].push(d[1]);
graph[d[1]].push(d[0]);
}
const dfs = (cur, color = 0) => {
colors[cur] = color;
for (const nxt of graph[cur]) {
if (colors[nxt] !== -1 && colors[nxt] === color) return false; // conflict
if (colors[nxt] === -1 && !dfs(nxt, color ^ 1)) return false;
}
return true;
};
for (let i = 0; i < N; ++i)
if (colors[i] === -1 && !dfs(i, 0)) return false;
return true;
};
dfs+染色法,先转换成图,然后创建一个colors数组来对每一个人进行判断是哪个组,先假定第一个人是1组,然后去找和第一个人不相关的人全部标为2组,同时判断可以不可以这样,如果不可以就代表没发二分图。
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
def dfs(n, colors, color, graph, i):
colors[i] = color
for j in range(n):
if graph[i][j] == 1:
if colors[j] == color:
return False
if colors[j] == 0 and not dfs(n, colors, -1*color, graph, j):
return False
return True
colors = [0]*n
graph = [[0]*n for _ in range(n)]
for a,b in dislikes:
graph[a-1][b-1] = 1
graph[b-1][a-1] = 1
for i in range(n):
if colors[i] == 0 and not dfs(n, colors, 1, graph, i):
return False
return True
时间复杂度:O(n+v)因为是染色的数组进行边的便利,同时不会撤销染色 空间复杂度:O(n^2)
本质上就是判断二分图。二分图形象理解:可以用两种颜色(比如-1,1)代表这两个集合,相邻的顶点不能是同一种颜色。
举例,构建一个图,这显然不是二分图(最明显的就是 A、C、D 这三个顶点有问题):
比如 A 是 1(belong),B、C、D 就是-1(-1*belong),但是对于第三行 C(-1)来讲,要求 A、D、G 都是 1,就矛盾了,无法构成二分图。
var possibleBipartition = function (N, dislikes) {
let map = {};
let group = new Array(N + 1).fill(0);
// 构建图 -> 邻接表
for (let [a, b] of dislikes) {
if (map.hasOwnProperty(a)) {
map[a].push(b);
} else {
map[a] = [b];
}
if (map.hasOwnProperty(b)) {
map[b].push(a);
} else {
map[b] = [a];
}
}
// 遍历每个 person
for (let i = 1; i <= N; i++) {
if (group[i] === 0 && !helper(i, map, group, 1)) {
return false;
}
}
return true;
};
// 染色,不符合二分图的自然是 false
let helper = (person, map, group, belong) => {
if (group[person] !== 0) {
if (group[person] !== belong) {
return false;
} else {
return true;
}
}
if (!map[person]) {
group[person] = belong;
return true;
}
group[person] = belong;
for (let val of map[person]) {
if (!helper(val, map, group, -1 * belong)) {
return false;
}
}
return true;
};
判断二分图,利用dfs对节点进行上色,若整个图都能上色那就能够分成二分图 ···cpp class Solution {
enum COLOR {UNCOLOR,RED,GREEN};//定义颜色;
public:
bool possibleBipartition(int n, vector<vector
bool isBinarypart(vector<vector<int>>& graph)
{
int n = graph.size();
vector<int> allcolor(n,UNCOLOR);//初始化节点的颜色为无色
function<bool(int,int)> dfs = [&](int node, int color)
{
if(allcolor[node] != UNCOLOR)//将当前节点与应该出现的颜色进行对比
{
return allcolor[node] == color;
}
allcolor[node] = color;//赋给节点值
int next_color = color == RED ? GREEN : RED;
for(auto& v:graph[node])
{
if(!dfs(v, next_color))
{
return false;
}
}
return true;
};
for(int i =0; i< n;i++)
{
if(allcolor[i] == UNCOLOR && !dfs(i,RED))
{
return false;
}
}
return true;
}
};
思路:二分图、染色法、图的建立和遍历、colors 数组
代码
class Solution:
def dfs(self, graph, colors, i, color, N):
colors[i] = color
for j in range(N):
# dislike eachother
if graph[i][j] == 1:
if colors[j] == color:
return False
if colors[j] == 0 and not self.dfs(graph, colors, j, -1 * color, N):
return False
return True
def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
graph = [[0] * N for i in range(N)]
colors = [0] * N
for a, b in dislikes:
graph[a - 1][b - 1] = 1
graph[b - 1][a - 1] = 1
for i in range(N):
if colors[i] == 0 and not self.dfs(graph, colors, i, 1, N):
return False
return True
var possibleBipartition = function(n, dislikes) { const graph = new Array(n).fill(0).map(() => new Array(n).fill(0)); const colors = new Array(n).fill(0); const dfs = (i, color, n) => { colors[i] = color; for (let j = 0; j < n; j++) { if (graph[i][j] == 1) { if (colors[j] == color) { return false; } if (colors[j] == 0 && !dfs(j, -1 * color, n)) { return false; } } } return true; } for (let [a, b] of dislikes) { graph[a - 1][b - 1] = 1; graph[b - 1][a - 1] = 1; } for (let i = 0; i < n; i++) { if (colors[i] == 0 && !dfs(i, 1, n)) { return false; } } return true; };
···python from enum import Enum
class Color(Enum): WHITE = 0 RED = 1 GREEN = 2
class Solution: def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool: graph = [[] for _ in range(n + 1)] colors = [Color.WHITE] * (n + 1)
for u, v in dislikes:
graph[u].append(v)
graph[v].append(u)
# reduce to 785. Is Graph Bipartite?
def isValidColor(u: int, color: Color) -> bool:
# the painted color should be same as the `color`
if colors[u] != Color.WHITE:
return colors[u] == color
colors[u] = color # always paint w/ `color`
# all children should have valid colors
childrenColor = Color.RED if colors[u] == Color.GREEN else Color.GREEN
return all(isValidColor(v, childrenColor) for v in graph[u])
return all(colors[i] != Color.WHITE or isValidColor(i, Color.RED)
for i in range(1, n + 1))
O(V+E) time, O(V) space
public boolean possibleBipartition(int n, int[][] dislikes) { int[][] graph = new int[n+1][n+1]; // 邻接矩阵初始化 for (int[] dislike : dislikes) { graph[dislike[0]][dislike[1]] = 1; graph[dislike[1]][dislike[0]] = 1; } int[] color = new int[n + 1]; // -1 1 表示两种颜色 0表示未被染色 for (int i = 1; i <= n; i++) { if(color[i] == 0) { // 未被染色过 就 dfs一次 每次彻底的dfs之后 剩下的和之前的不是一个联通分量的 第一个节点随便赋值1 还是 -1 if(!dfs(graph, i, color)) return false; } } return true; }
public boolean dfs(int[][] graph, int start, int[] color) {
color[start] = color[start] == 0 ? 1 : color[start]; // 外层for中第一次进入 每次第一个值赋值是1 还是 -1 都不要紧 关键是一个联通分量里面交替染色不能有同色的
// 这里的关键是将联通的节点交替染色
for (int i = 1; i < color.length; i++) {
if(graph[start][i] == 1) {
if(color[i] == color[start]) {
return false; // dfs下去不能相同
}
if(color[i] == 0) {
color[i] = -1 * color[start];
if(!dfs(graph, i, color)) return false;
}
}
}
return true;
}
var possibleBipartition = function(N, dislikes) {
const map = new Uint16Array(N+1).fill(2047);
let counter = 0;
const len = dislikes.length;
for(let i = 0;i < len; i++){
const A = map[dislikes[i][0]], B = map[dislikes[i][1]];
const AP = A + (A % 2 ? -1 : 1), BP = B + (B % 2 ? -1 : 1);
if(A===2047){
if(B===2047){
map[dislikes[i][0]] = counter++;
map[dislikes[i][1]] = counter++;
} else {
map[dislikes[i][0]] = BP;
}
} else if(B===2047){
map[dislikes[i][1]] = AP;
} else{
if(A===B) return false;
if(A===BP) continue;
for(let j = 1; j<=N; j++){
map[j] === B ? map[j] = AP :
map[j] === BP ? map[j] = A :
null;
}
}
}
return true;
};
图的问题没有接触过,所以这道题基本是看题解做的 思路: 1、先建图:用邻接矩阵构建图 2、尝试对每个结点染色,如果当前结点没有被染色过,对其进行染色,并递归对其讨厌的结点染另一种颜色, 在染色过程中如果发现其讨厌的点已经被染过跟自己一样的颜色或者对其染相反的颜色失败, 则证明无法进行二分
class Solution {
public:
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
graph = vector<vector<int>>(n);
// 构造邻接矩阵
for (auto &item : dislikes) {
graph[item[0] - 1].push_back(item[1] - 1);
graph[item[1] - 1].push_back(item[0] - 1);
}
// 0: 没颜色, 1: 染成红色, -1: 染成蓝色
colors = vector<int>(n, 0);
for (int i = 0; i < n; i++) {
if (colors[i] == 0 && !dfs(i, 1)) {
return false;
}
}
return true;
}
bool dfs(int cur, int color)
{
colors[cur] = color;
for (int next : graph[cur]) {
if (colors[next] == color) {
return false;
}
if (colors[next] == 0 && !dfs(next, -color)) {
return false;
}
}
return true;
}
private:
vector<vector<int>> graph;
vector<int> colors;
};
复杂度分析 V 和 E 分别为图中的点和边的数目
class Solution {
vector<vector<int>> G;
vector<int> _colors;
public:
bool possibleBipartition(int n, vector<vector<int>>& dislikes)
{
G = vector<vector<int>>(n);
for (const auto& d : dislikes)
{
G[d[0] - 1].push_back(d[1] - 1);
G[d[1] - 1].push_back(d[0] - 1);
}
_colors = vector<int>(n, 0); // 0: 没颜色, 1: 染成红色, -1: 染成蓝色
for (int i = 0; i < n; i++)
if (_colors[i] == 0 && !dfs(i, 1))
return false;
return true;
}
bool dfs(int cur, int color)
{
_colors[cur] = color;
for (int next : G[cur])
{
if (_colors[next] == color)
return false;
if (_colors[next] == 0 && !dfs(next, -color))
return false;
}
return true;
}
};
class Solution {
ArrayList<Integer>[] graph;
Map<Integer, Integer> color;
public boolean possibleBipartition(int N, int[][] dislikes) {
graph = new ArrayList[N+1];
for (int i = 1; i <= N; ++i)
graph[i] = new ArrayList();
for (int[] edge: dislikes) {
graph[edge[0]].add(edge[1]);
graph[edge[1]].add(edge[0]);
}
color = new HashMap();
for (int node = 1; node <= N; ++node)
if (!color.containsKey(node) && !dfs(node, 0))
return false;
return true;
}
public boolean dfs(int node, int c) {
if (color.containsKey(node))
return color.get(node) == c;
color.put(node, c);
for (int nei: graph[node])
if (!dfs(nei, c ^ 1))
return false;
return true;
}
}
二分图 图的建立与遍历
var possibleBipartition = function (n, dislikes) {
let ok = true;
// 图节点编号从 1 开始
let color = new Array(n + 1).fill(false);
let visited = new Array(n + 1).fill(false);
const buildGraph = (n, dislikes) => {
// 图节点编号为 1...n
let graph = new Array(n + 1).fill(0).map(() => new Array());
for (let edge of dislikes) {
let v = edge[1];
let w = edge[0];
// 「无向图」相当于「双向图」
// v -> w
graph[v].push(w);
// w -> v
graph[w].push(v);
}
return graph;
};
const traverse = (graph, v) => {
if (!ok) return;
visited[v] = true;
for (let w of graph[v]) {
if (!visited[w]) {
/**
* 相邻节点 w 没有被访问过
* 那么应该给节点 w 涂上和节点 v 不同的颜色
*/
color[w] = !color[v];
// 继续遍历 w
traverse(graph, w);
} else {
/**
* 相邻节点 w 已经被访问过
* 根据 v 和 w 的颜色判断是否是二分图
*/
if (color[w] == color[v]) ok = false;
}
}
};
// 转化成邻接表表示图结构
const graph = buildGraph(n, dislikes);
for (let i = 1; i <= n; i++) {
if (!visited[i]) traverse(graph, i);
}
return ok;
};
时间复杂度: O(n+m)
空间复杂度: O(n+m)
深度优先遍历 邻接链表 从某一个顶点开始上色 对相邻的节点上相反的色 当出现某个节点被上两个不同的色的时候上色解决
时间复杂度:O(n + k) 空间复杂度:O(n + k)
class Solution {
ArrayList<Integer>[] graph;
Map<Integer, Integer> color;
public boolean possibleBipartition(int N, int[][] dislikes) {
graph = new ArrayList[N+1];
for (int i = 1; i <= N; ++i)
graph[i] = new ArrayList();
for (int[] edge: dislikes) {
graph[edge[0]].add(edge[1]);
graph[edge[1]].add(edge[0]);
}
color = new HashMap();
for (int node = 1; node <= N; ++node)
//如果当前顶点已被上色 则结束循环
//如果当前顶点未被上色 递归遍历顶点及相邻的订单
if (!color.containsKey(node) && !dfs(node, 0))
return false;
return true;
}
public boolean dfs(int node, int c) {
if (color.containsKey(node))
return color.get(node) == c;
//上色
color.put(node, c);
//递归检索相邻的定点 上相反的色
//深度优先遍历
for (int nei: graph[node])
if (!dfs(nei, c ^ 1))
return false;
return true;
}
}
class Solution {
public:
bool paint(int x, int c, vector<vector<int>>& edges, vector<int>& colors) {
if (colors[x] == c) return true;
else if (colors[x] != 0 && colors[x] != c) return false;
colors[x] = c;
int reversed = (c == 1 ? 2 : 1);
for (auto& e : edges[x]) {
if (!paint(e, reversed, edges, colors)) {
colors[x] = 0;
return false;
}
}
return true;
}
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
vector<vector<int>> edges(N);
for (auto e : dislikes) {
edges[e[0]-1].push_back(e[1]-1);
}
vector<int> colors(N, 0);
for (int i = 0; i < N; ++i) {
if(!paint(i, 1, edges, colors) && !paint(i, 2, edges, colors)) {
return false;
}
}
return true;
}
};
构建图,对图进行二分染色
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
color=[0]*(1+n)
graph = defaultdict(list)
for dislike in dislikes:
x,y=dislike
graph[x].append(y)
graph[y].append(x)
for i in range(1,n+1):
if color[i]==0:
color[i] = 1
queue=deque([i])
while queue:
curr = queue.popleft()
col = color[curr]
for neigbor in graph[curr]:
if col==color[neigbor]:
return False
if color[neigbor]==0:
color[neigbor]=-col
queue.append(neigbor)
return True
func possibleBipartition(n int, dislikes [][]int) bool {
graph := map[int][]int{}
for _, dislike := range dislikes {
graph[dislike[0]] = append(graph[dislike[0]], dislike[1])
graph[dislike[1]] = append(graph[dislike[1]], dislike[0])
}
color := make([]int, n+1)
for index := range color[1:] {
if color[index+1] == 0 {
color[index+1] = 1
queue := []int{}
queue = append(queue, index+1)
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
col := color[cur]
for _, neigbor := range graph[cur] {
if col == color[neigbor] {
return false
}
if color[neigbor] == 0 {
color[neigbor] = -col
queue = append(queue, neigbor)
}
}
}
}
}
return true
}
时间复杂度:O(N+E)
空间复杂度:O(N)
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
if not dislikes:
return True
if not n:
return False
## 不能有环
graph = [[0] * n for _ in range(n)]
for a,b in dislikes:
graph[a-1][b-1] = 1
graph[b-1][a-1] = 1
colors = [0] * n
for i in range(n):
if colors[i] == 0 and not self.dfs(n, i, graph, 1, colors):
return False
return True
def dfs(self, n, i, graph, color, colors):
colors[i] = color
for j in range(n):
if graph[i][j] == 1 and colors[j] == color:
return False
if graph[i][j] == 1 and colors[j] == 0:
colors[j] = -1 * color
if self.dfs(n, j, graph, -1 * color, colors) is False:
return False
return True
class Solution {
private:
bool dfs(int u, const vector<vector<int>> &graph, vector<int> &col) {
for (int v : graph[u])
if (col[v] == -1) {
col[v] = 1 - col[u];
if (!dfs(v, graph, col))
return false;
} else if (col[v] == col[u])
return false;
return true;
}
public:
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
vector<vector<int>> graph(N);
for (const auto &v : dislikes) {
int x = v[0] - 1, y = v[1] - 1;
graph[x].push_back(y);
graph[y].push_back(x);
}
vector<int> col(N, -1);
for (int i = 0; i < N; i++)
if (col[i] == -1) {
col[i] = 0;
if (!dfs(i, graph, col))
return false;
}
return true;
}
};
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
q = deque()
color = [None for i in range(n)]
graph = [[] for i in range(n)]
for i,j in dislikes:
graph[i-1].append(j-1)
graph[j-1].append(i-1)
for i in range(n):
if color[i]==None:
q.append(i)
color[i] = True
while len(q):
current = q.popleft()
for nei in graph[current]:
if color[nei]==color[current]:
return False
if color[nei]==None:
q.append(nei)
color[nei] = not color[current]
return True
Language: Java
public boolean possibleBipartition(int n, int[][] dislikes) {
boolean[][] graph = new boolean[n][n];
for (int[] d : dislikes) {
graph[d[0] - 1][d[1] - 1] = true;
graph[d[1] - 1][d[0] - 1] = true;
}
// Use an int array to represent groups.
// 0 is not grouped, 1 and -1 represent two groups
int[] colors = new int[n];
for (int u = 0; u < n; u++) {
// The loop ensures all nodes are handled when the graph is not connected
if (colors[u] == 0 && !paint(u, 1, colors, graph)) {
return false;
}
}
return true;
}
private boolean paint(int u, int color, int[] colors, boolean[][] graph) {
// Return if it is feasible to paint "u" to "color"
if (colors[u] != 0) {
// u already has a group, check if we are assign it to another group
return colors[u] == color;
}
// Paint "u" with "color" (assign group), then DFS
colors[u] = color;
for (int v = 0; v < colors.length; v++) {
if (graph[u][v] && !paint(v, -color, colors, graph)) {
return false;
}
}
return true;
}
A graph is bipartite if and only if it is 2-colorable
class Solution {
public boolean possibleBipartition(int n, int[][] dislikes) {
boolean[][] graph = new boolean[n][n];
int[] colors = new int[n];
for (int[] arr : dislikes) {
graph[arr[0]-1][arr[1]-1] = true;
graph[arr[1]-1][arr[0]-1] = true;
}
for (int i = 0; i < graph.length; i++) {
if (colors[i] == 0 && !dfs(i, 1, graph, colors)) {
return false;
}
}
return true;
}
public boolean dfs(int i, int color, boolean[][] graph, int[] colors) {
if (colors[i] != 0) {
return colors[i] == color;
}
colors[i] = color;
for (int j = 0; j < graph.length; j++) {
if (graph[i][j] && !dfs(j, -color, graph, colors)) {
return false;
}
}
return true;
}
}
Time: O(V+E) Space: O($V^2$)
class Solution {
public:
bool paint(int x, int c, vector<vector
def possibleBipartition(self, N, dislikes):
graph = collections.defaultdict(list)
for u, v in dislikes:
graph[u].append(v)
graph[v].append(u)
color = {}
def dfs(node, c = 0):
if node in color:
return color[node] == c
color[node] = c
return all(dfs(nei, c ^ 1) for nei in graph[node])
return all(dfs(node)
for node in range(1, N+1)
if node not in color)
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
graph = defaultdict(list)
for i,j in dislikes:
graph[i].append(j)
graph[j].append(i)
color = {}
def dfs(node,c):
if node in color: # 若node已经上色则看是否上色正确
return color[node]==c
color[node]=c # 上色
for nxt in graph[node]:
if not dfs(nxt,c^1): # 给下一个节点上色
return False
return True
for i in range(1,n+1): # 对n人遍历
if i not in color: # 还未上色
if not dfs(i, c=0): # 从node开始深度遍历
return False
return True
图 着色
class Solution:
def __init__(self):
self.ok = True
self.color = []
self.visited = []
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
self.color = [1 for _ in range(n + 1)]
self.visited = [False for _ in range(n + 1)]
adj = defaultdict(list)
for a, b in dislikes:
adj[a].append(b)
adj[b].append(a)
for i in range(1, n + 1):
if not self.ok:
return False
if not self.visited[i]:
self.dfs(adj, i)
return True
def dfs(self, adj, i):
if not self.ok: return
self.visited[i] = True
for child in adj[i]:
if self.visited[child]:
if self.color[i] == self.color[child]:
self.ok = False
else:
self.color[child] = -self.color[i]
self.dfs(adj, child)
-
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
# 初始化图
graph = [[] for _ in range(n+1)]
# 状态
status = [-1] * (n+1)
# 将两个不喜欢的元素存入彼此的位置
for u, v in dislikes:
graph[u].append(v)
graph[v].append(u)
for i in range(1, n+1):
if status[i] == -1:
# 当前的分组
status[i] = 0
color = 1
# 创建一个i对应的不喜欢的队列
queue = deque([i])
while queue:
for _ in range(len(queue)):
cur = queue.popleft()
for ni in graph[cur]:
# 如果当前的分组是-1, 那么就令状态为染色1
if status[ni] == -1:
status[ni] = color
# 将当前元素放入队列
queue.append(ni)
# 如果当前的分组状态和存放它的不喜欢元素的图中的元素的染色一样的话,那么矛盾返回False
elif status[cur] == status[ni]:
return False
# 如果color等于1(0),那么color等于0(1)
color ^= 1
return True
var possibleBipartition = function (n, dislikes) {
if (dislikes.length === 0) return true;
const adjList = {};
const visited = {};
// init
for (let i = 1; i <= n; i++) {
adjList[i] = [];
visited[i] = 0;
}
// build adjList
for (let i = 0; i < dislikes.length; i++) {
let [p1, p2] = dislikes[i];
adjList[p1].push(p2);
adjList[p2].push(p1);
}
// bfs
for (let i = 1; i <= n; i++) {
if (visited[i] !== 0) continue;
const queue = [i];
visited[i] = 1;
while (queue.length > 0) {
let dequeue = queue.shift();
let currLabel = visited[dequeue];
let neighborLabel = currLabel === 1 ? 2 : 1;
for (let neighbor of adjList[dequeue]) {
if (!visited[neighbor]) {
visited[neighbor] = neighborLabel;
queue.push(neighbor);
} else {
if (visited[neighbor] !== neighborLabel) return false;
}
}
}
}
return true;
};
/*
Adjacent list:
Time: O(n) + O(dislikes.length) + O(V + E), V = n, E = dislikes.length,
O(n + dislikes.length)
Space: O(V + E) for graph, O(V) for visited, dfs stack O(V)
*/
class Solution {
// adjacent list
public boolean possibleBipartition(int n, int[][] dislikes) {
Set<Integer>[] graph = new HashSet[n]; // syntax!
// build graph
for (int i = 0; i < n; i++) {
graph[i] = new HashSet<>();
}
for (int[] dislike : dislikes) {
int a = dislike[0], b = dislike[1];
graph[a - 1].add(b - 1); // note: off by 1 here
graph[b - 1].add(a - 1);
}
int color = 1;
int[] visited = new int[n];
// check
for (int person = 0; person < n; person++) {
if (visited[person] == 0 && !dfs(graph, visited, color, person, n)) {
return false;
}
}
return true;
}
private boolean dfs(Set<Integer>[] graph, int[] visited, int color, int person, int n) {
visited[person] = color;
// only for that set, no need for 0 ~ n-1
for (int i : graph[person]) {
if (graph[person].contains(i)) { // hater check
if (visited[i] == color) {
return false;
}
else if (visited[i] == 0 && !dfs(graph, visited, -color, i, n)) {
return false;
}
}
}
return true;
}
}
把每个人当作成一个节点,讨厌的关系当作成图中的边。因为互相讨厌的人不能放在同一组里,相当于图中的所有相邻节点都要放进两个不同的组,所以题目就可转变成二分图的染色问题。
/**
* @param {number} n
* @param {number[][]} dislikes
* @return {boolean}
*/
var possibleBipartition = function(n, dislikes) {
// 动态创建二维数组
let graph = [...Array(n + 1)].map(() => Array());
let colors = Array(n + 1).fill(-1)
// 建无向图
for (const d of dislikes) {
graph[d[0]].push(d[1])
graph[d[1]].push(d[0])
}
let dfs = (cur, color = 0) => {
colors[cur] = color
for (let nxt of graph[cur]) {
if (colors[nxt] !== -1 && colors[nxt] === color) {
return false;
}
if (colors[nxt] === -1 && !dfs(nxt, color ^ 1)) {
return false;
}
}
return true
};
for (let i = 0; i < n; i++) {
if (colors[i] === -1 && !dfs(i, 0)){
return false;
}
}
return true
};
class Solution(object):
def possibleBipartition(self, N, dislikes):
graph = collections.defaultdict(list)
for u, v in dislikes:
graph[u].append(v)
graph[v].append(u)
color = {}
def dfs(node, c = 0):
if node in color:
return color[node] == c
color[node] = c
return all(dfs(nei, c ^ 1) for nei in graph[node])
return all(dfs(node)
for node in range(1, N+1)
if node not in color)
二分标记
var possibleBipartition = function(n, dislikes) {
let res=true;
//建图
let graph=new Array(n+1).fill(0).map(()=>new Array(n+1).fill(0));
for (let i = 0; i < dislikes.length; i++) {
let a=dislikes[i][0];
let b=dislikes[i][1];
graph[a][b]=1;
graph[b][a]=1;
}
//创建标记色卡
let colors=new Array(n+1).fill(0);
//创建颜色(二分)01
let color=1;
//遍历标记
for (let i = 1; i <= colors.length; i++) {
//如果未标记
if (colors[i]===0){
dfs(graph,colors,color,i);
}
}
return res;
};
//graph图 colors标记记录 color当前颜色 i第i个人
var dfs=function (graph,colors,color,i){
//如果不能二分,直接返回
if (res===false) return res;
//遍历相邻的点
for(let j=1;j<colors.length;j++){
//判断是不是下一个相邻的点
if (graph[i][j]===1){
//如果没有标记过
if (colors[j]===0){
//标记为当前颜色
colors[j]=color;
dfs(graph,colors,-1*color,j)
}
//如果当前的记录点颜色和当前颜色相同,返回false
if (colors[j]===color) {
res=false;
return res;
}
}
}
return res;
}
补:
vector
colors=vector<int>(n,0);
for(int i=0;i<colors.size();i++)
{
if(colors[i]==0 && !dfs(i,1))
return false;
}
return true;
}
bool dfs(int cur, int color)
{
colors[cur]=color;
for(int next:G[cur])
{
if(colors[next]==color)
return false;
if(colors[next]==0 && !dfs(next,-color))
return false;
}
return true;
}
对图进行染色
def dfs(self, graph, colors, i, color, n):
colors[i] = color
for j in range(n):
if graph[i][j] == 1:
if colors[j] == color:
return False
if colors[j] == 0 and not self.dfs(graph, colors, j, -1 * color, n):
return False
return True
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
graph = [[0] * n for i in range(n)]
colors = [0] * n
for a, b in dislikes:
graph[a - 1][b - 1] = 1
graph[b - 1][a - 1] = 1
for i in range(n):
if colors[i] == 0 and not self.dfs(graph, colors, i, -1, n):
return False
return True
时间 O(V+E) \ 空间 O(v^^2)
https://leetcode-cn.com/problems/possible-bipartition/
给定一组 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 中每一组都 不同
C++ Code:
class Solution {
public:
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
if (dislikes.size() <= 1) return true;
list<int> adjList[n+1];
vector<int> color(n+1);
vector<int> visited(n+1);
for (auto v : dislikes) {
// build adjacent list for the graph
adjList[v[0]].push_back(v[1]);
}
displayAdjList(adjList, 1);
queue<int> q;
q.push(1);
color[1] = 1;
list<int> :: iterator it;
int i;
while (!q.empty()) {
i = q.front();
cout << "checking "<<q.front()<<endl;
q.pop();
if (visited[i] == 1) continue;
visited[i] = 1;
for(it = adjList[i].begin(); it != adjList[i].end(); ++it) {
// check if color conflict
if (color[*it] == color[i])
return false;
// assign *it different color to i's
color[*it] = (color[i] == 1) ? 2 : 1;
displayColor(color);
// push i'th neighbor to q
q.push(*it);
}
}
return true;
}
void displayAdjList(list<int> adj_list[], int v) {
for(int i = 1; i<=v; i++) {
cout << i << "--->";
list<int> :: iterator it;
for(it = adj_list[i].begin(); it != adj_list[i].end(); ++it) {
cout << *it << " ";
}
cout << endl;
}
}
void displayColor(vector<int> c) {
cout<<"color:";
for (auto v:c) {
cout<<v<<' ';
}
cout<<endl;
}
};
复杂度分析
令 n 为数组长度。
dfs搜索
class Solution {
public:
bool paint(int x, int c, vector<vector<int>>& edges, vector<int>& colors) {
if (colors[x] == c) return true;
else if (colors[x] != 0 && colors[x] != c) return false;
colors[x] = c;
int reversed = (c == 1 ? 2 : 1);
for (auto& e : edges[x]) {
if (!paint(e, reversed, edges, colors)) {
colors[x] = 0;
return false;
}
}
return true;
}
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
vector<vector<int>> edges(N);
for (auto e : dislikes) {
edges[e[0]-1].push_back(e[1]-1);
}
vector<int> colors(N, 0);
for (int i = 0; i < N; ++i) {
if(!paint(i, 1, edges, colors) && !paint(i, 2, edges, colors)) {
return false;
}
}
return true;
}
};
https://leetcode-cn.com/problems/possible-bipartition/
给定一组 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 中每一组都 不同
图论
二分染色
BFS or DFS Becase dislikes.length 远小于2^n, 是稀疏图,用adjacent List build graph. Since it does not have direction, so have to push v-->u, u-->v for one dislikes[i]
class Solution {
public:
bool possibleBipartition(int n, vector<vector
q.push(v+1);
color[v+1] = 1; // here picking 1 or -1 does not matter
while (!q.empty()) {
i = q.front(); q.pop();
for(it = adjList[i].begin(); it != adjList[i].end(); ++it) {
// check if color conflict
if (color[*it] == color[i])
return false;
if (color[*it] != 0) continue;
// assign *it different color to i's
color[*it] = -color[i];
q.push(*it);
}
}
}
return true;
}
};
**复杂度分析**
令 n 为数组长度。
- 时间复杂度:$O(n+e)$
- 空间复杂度:$O(n+e)$
Day30
1、二分图的染色问题
2、建立图
3、遍历图,并染色
4、如果相邻边出现相同颜色,返回false,始终保持不同颜色,返回true
const possibleBipartition = (N, dislikes) => {
let graph = [...Array(N + 1)].map(() => Array()), // 动态创建二维数组
colors = Array(N + 1).fill(-1)
// build the undirected graph
for (const d of dislikes) {
graph[d[0]].push(d[1])
graph[d[1]].push(d[0])
}
const dfs = (cur, color = 0) => {
colors[cur] = color
for (const nxt of graph[cur]) {
if (colors[nxt] !== -1 && colors[nxt] === color) return false // conflict
if (colors[nxt] === -1 && !dfs(nxt, color ^ 1)) return false;
}
return true
};
for (let i = 0; i < N; ++i)
if (colors[i] === -1 && !dfs(i, 0)) return false
return true
};
时间复杂度:O(n)
空间复杂度:O(n)
886. 可能的二分法
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/possible-bipartition/
前置知识
题目描述
每个人都可能不喜欢其他人,那么他们不应该属于同一组。
形式上,如果 dislikes[i] = [a, b],表示不允许将编号为 a 和 b 的人归入同一组。
当可以用这种方法将每个人分进两组时,返回 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 <= 10000 dislikes[i].length == 2 1 <= dislikes[i][j] <= N dislikes[i][0] < dislikes[i][1] 对于dislikes[i] == dislikes[j] 不存在 i != j