Possible Bipartition - Leetcode Solution

Possible Bipartition is a graph problem on LeetCode. The problem statement is as follows:

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.

Solution:

This is a graph problem where we need to check if the graph can be divided into two disjoint sets such that there is no edge within the sets. We need to use the concept of bipartite graphs to solve this problem.

A bipartite graph is a graph whose vertices can be divided into two disjoint sets, U and V, such that every edge connects a vertex in U to one in V.

We can use the idea of color-coding to check if the graph is bipartite or not. We can assign colors to the vertices such that no two adjacent vertices have the same color.

We can start with any vertex and assign it a color, then we can assign a different color to all its neighbors. We can continue this process recursively for all the vertices. If at any point we find that two adjacent vertices have the same color, then the graph is not bipartite.

Algorithm:

1. Create a graph with adjacency list from dislikes[].
2. Initialize visited[] with false for all vertices.
3. For every vertex, if it is not visited yet call dfs() function.
4. At each step, assign the vertex the opposite color of its parent node or its initial color if it does not have a parent.
5. If you encounter an adjacent vertex with the same color as the parent node, return false.
6. If the dfs() function terminates successfully, return true.

Code:

Here is the Python code for the solution:

class Solution: def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool: graph = [[] for _ in range(N+1)] for u, v in dislikes: graph[u].append(v) graph[v].append(u) color = [0] * (N+1) def dfs(node, c): color[node] = c for nei in graph[node]: if color[nei] == c: return False if color[nei] == 0 and not dfs(nei, -c): return False return True for i in range(1, N+1): if color[i] == 0 and not dfs(i, 1): return False return True

Time Complexity: O(N+E), where N is the number of vertices and E is the number of edges.

Space Complexity: O(N+E), where N is the number of vertices and E is the number of edges.

1