Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/886.html
886. Possible Bipartition (Medium)
Given a set of N
people (numbered 1, 2, ..., N
), we would like to split everyone into two groups of any size.
Each person may dislike some other people, and they should not go into the same group.
Formally, if dislikes[i] = [a, b]
, it means it is not allowed to put the people numbered a
and b
into the same group.
Return true
if and only if it is possible to split everyone into two groups in this way.
Example 1:
Input: N = 4, dislikes = [[1,2],[1,3],[2,4]] Output: true Explanation: group1 [1,4], group2 [2,3]
Example 2:
Input: N = 3, dislikes = [[1,2],[1,3],[2,3]] Output: false
Example 3:
Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]] Output: false
Note:
1 <= N <= 2000
0 <= dislikes.length <= 10000
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
- There does not exist
i != j
for whichdislikes[i] == dislikes[j]
.
Related Topics:
Depth-first Search
Solution 1. DFS
// OJ: https://leetcode.com/problems/possible-bipartition/
// Time: O(V + E)
// Space: O(V + E)
class Solution {
vector<unordered_set<int>> G;
vector<int> id;
bool dfs(int u, int prev = 1) {
if (id[u]) return id[u] != prev;
id[u] = -prev;
for (int v : G[u]) {
if (!dfs(v, id[u])) return false;
}
return true;
}
public:
bool possibleBipartition(int N, vector<vector<int>>& A) {
G.assign(N + 1, {});
id.assign(N + 1, 0);
for (auto &v : A) {
G[v[0]].insert(v[1]);
G[v[1]].insert(v[0]);
}
for (int i = 1; i <= N; ++i) {
if (id[i]) continue;
if (!dfs(i)) return false;
}
return true;
}
};
Solution 2. BFS
// OJ: https://leetcode.com/problems/possible-bipartition/
// Time: O(V + E)
// Space: O(V + E)
class Solution {
public:
bool possibleBipartition(int N, vector<vector<int>>& A) {
vector<vector<int>> G(N + 1);
vector<int> id(N + 1, 0);
for (auto &v : A) {
G[v[0]].push_back(v[1]);
G[v[1]].push_back(v[0]);
}
queue<int> q;
for (int i = 1; i <= N; ++i) {
if (id[i]) continue;
q.push(i);
id[i] = 1;
while (q.size()) {
int u = q.front();
q.pop();
for (int v : G[u]) {
if (id[v]) {
if (id[v] != -id[u]) return false;
else continue;
}
id[v] = -id[u];
q.push(v);
}
}
}
return true;
}
};
-
class Solution { public boolean possibleBipartition(int N, int[][] dislikes) { int[] degrees = new int[N]; Map<Integer, Set<Integer>> dislikesMap = new HashMap<Integer, Set<Integer>>(); for (int[] dislike : dislikes) { int person1 = dislike[0] - 1, person2 = dislike[1] - 1; degrees[person1]++; degrees[person2]++; Set<Integer> dislikesSet1 = dislikesMap.getOrDefault(person1, new HashSet<Integer>()); Set<Integer> dislikesSet2 = dislikesMap.getOrDefault(person2, new HashSet<Integer>()); dislikesSet1.add(person2); dislikesSet2.add(person1); dislikesMap.put(person1, dislikesSet1); dislikesMap.put(person2, dislikesSet2); } int[] groups = new int[N]; for (int i = 0; i < N; i++) { if (degrees[i] > 0 && groups[i] == 0) { groups[i] = 1; boolean possible = breadthFirstSearch(dislikesMap, groups, i); if (!possible) return false; } } return true; } public boolean breadthFirstSearch(Map<Integer, Set<Integer>> dislikesMap, int[] groups, int start) { Queue<Integer> queue = new LinkedList<Integer>(); queue.offer(start); while (!queue.isEmpty()) { int person = queue.poll(); int group = groups[person]; int newGroup = 3 - group; Set<Integer> dislikes = dislikesMap.getOrDefault(person, new HashSet<Integer>()); for (int dislike : dislikes) { if (groups[dislike] == group) return false; else if (groups[dislike] == 0) { groups[dislike] = newGroup; queue.offer(dislike); } } } return true; } } ############ class Solution { private int[] p; public boolean possibleBipartition(int n, int[][] dislikes) { p = new int[n]; List<Integer>[] g = new List[n]; Arrays.setAll(g, k -> new ArrayList<>()); for (int i = 0; i < n; ++i) { p[i] = i; } for (var e : dislikes) { int a = e[0] - 1, b = e[1] - 1; g[a].add(b); g[b].add(a); } for (int i = 0; i < n; ++i) { for (int j : g[i]) { if (find(i) == find(j)) { return false; } p[find(j)] = find(g[i].get(0)); } } return true; } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } }
-
// OJ: https://leetcode.com/problems/possible-bipartition/ // Time: O(V + E) // Space: O(V + E) class Solution { vector<unordered_set<int>> G; vector<int> id; bool dfs(int u, int prev = 1) { if (id[u]) return id[u] != prev; id[u] = -prev; for (int v : G[u]) { if (!dfs(v, id[u])) return false; } return true; } public: bool possibleBipartition(int N, vector<vector<int>>& A) { G.assign(N + 1, {}); id.assign(N + 1, 0); for (auto &v : A) { G[v[0]].insert(v[1]); G[v[1]].insert(v[0]); } for (int i = 1; i <= N; ++i) { if (id[i]) continue; if (!dfs(i)) return false; } return true; } };
-
class Solution: def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] g = defaultdict(list) for a, b in dislikes: a, b = a - 1, b - 1 g[a].append(b) g[b].append(a) p = list(range(n)) for i in range(n): for j in g[i]: if find(i) == find(j): return False p[find(j)] = find(g[i][0]) return True ############ class Solution(object): def possibleBipartition(self, N, dislikes): """ :type N: int :type dislikes: List[List[int]] :rtype: bool """ graph = collections.defaultdict(list) for dislike in dislikes: graph[dislike[0] - 1].append(dislike[1] - 1) graph[dislike[1] - 1].append(dislike[0] - 1) color = [0] * N for i in range(N): if color[i] != 0: continue bfs = collections.deque() bfs.append(i) color[i] = 1 while bfs: cur = bfs.popleft() for e in graph[cur]: if color[e] != 0: if color[cur] == color[e]: return False else: color[e] = -color[cur] bfs.append(e) return True
-
func possibleBipartition(n int, dislikes [][]int) bool { p := make([]int, n) g := make([][]int, n) for i := range p { p[i] = i } for _, e := range dislikes { a, b := e[0]-1, e[1]-1 g[a] = append(g[a], b) g[b] = append(g[b], a) } var find func(int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } for i := 0; i < n; i++ { for _, j := range g[i] { if find(i) == find(j) { return false } p[find(j)] = find(g[i][0]) } } return true }
-
function possibleBipartition(n: number, dislikes: number[][]): boolean { const color = new Array(n + 1).fill(0); const g = Array.from({ length: n + 1 }, () => []); const dfs = (i: number, v: number) => { color[i] = v; for (const j of g[i]) { if (color[j] === color[i] || (color[j] === 0 && dfs(j, 3 ^ v))) { return true; } } return false; }; for (const [a, b] of dislikes) { g[a].push(b); g[b].push(a); } for (let i = 1; i <= n; i++) { if (color[i] === 0 && dfs(i, 1)) { return false; } } return true; }
-
impl Solution { fn dfs(i: usize, v: usize, color: &mut Vec<usize>, g: &Vec<Vec<usize>>) -> bool { color[i] = v; for &j in (*g[i]).iter() { if color[j] == color[i] || color[j] == 0 && Self::dfs(j, v ^ 3, color, g) { return true; } } false } pub fn possible_bipartition(n: i32, dislikes: Vec<Vec<i32>>) -> bool { let n = n as usize; let mut color = vec![0; n + 1]; let mut g = vec![Vec::new(); n + 1]; for d in dislikes.iter() { let (i, j) = (d[0] as usize, d[1] as usize); g[i].push(j); g[j].push(i); } for i in 1..=n { if color[i] == 0 && Self::dfs(i, 1, &mut color, &g) { return false; } } true } }