886. Possible Bipartition
Explanation:
To solve this problem, we can use a graph coloring approach. We can create a graph where each person is a node, and an edge between two nodes represents a dislike relationship. We then try to color the nodes (people) with two colors such that no two connected nodes have the same color.
If we can successfully color all nodes with two colors without any conflicts, then it is possible to split everyone into two groups. If at any point we encounter a conflict where two connected nodes have the same color, then it is not possible to split them into two groups.
We can use a depth-first search (DFS) algorithm to traverse the graph and color the nodes. We start by assigning the color 0 to the first node and its disliked nodes with color 1, and vice versa. Then, we continue coloring the nodes by visiting each node and assigning the opposite color to its neighbors. If we encounter a conflict during this process, we return false. :
class Solution {
public boolean possibleBipartition(int n, int[][] dislikes) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
for (int[] dislike : dislikes) {
graph.get(dislike[0]).add(dislike[1]);
graph.get(dislike[1]).add(dislike[0]);
}
int[] colors = new int[n + 1];
for (int i = 1; i <= n; i++) {
if (colors[i] == 0 && !dfs(graph, colors, i, 1)) {
return false;
}
}
return true;
}
private boolean dfs(List<List<Integer>> graph, int[] colors, int node, int color) {
if (colors[node] != 0) {
return colors[node] == color;
}
colors[node] = color;
for (int neighbor : graph.get(node)) {
if (!dfs(graph, colors, neighbor, -color)) {
return false;
}
}
return true;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.