We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.
Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true 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: The first group has [1,4], and the second group has [2,3].
Example 2:
Input: n = 3, dislikes = [[1,2],[1,3],[2,3]] Output: false Explanation: We need at least 3 groups to divide them. We cannot put them in two groups.
Constraints:
1 <= n <= 20000 <= dislikes.length <= 104dislikes[i].length == 21 <= ai < bi <= ndislikes are unique.This approach uses a BFS traversal to determine if the graph is bipartite. A graph is bipartite if you can color it using two colors such that no two adjacent nodes have the same color. We'll represent people as nodes and dislikes as edges.
The C solution uses a BFS approach to check if the graph can be bipartite. The graph is represented using an adjacency list, and BFS is performed from each uncolored node. If we find a conflict in colors, we return false.
C++
Java
Python
C#
JavaScript
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges.
Space Complexity: O(V + E) for storing the graph structure.
This approach uses a DFS traversal to determine if the graph is bipartite. Similar to BFS, DFS attempts to color the graph using two colors to check if a valid bipartition is possible.
The C solution uses a recursive DFS approach to attempt coloring with two colors. If two adjacent nodes have the same color during the traversal, the graph is not bipartite.
C++
Java
Python
C#
JavaScript
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges.
Space Complexity: O(V + E) for graph representation.
| Approach | Complexity |
|---|---|
| Approach 1: Graph Coloring Using BFS | Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. |
| Approach 2: Graph Coloring Using DFS | Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. |
Possible Bipartition | Bipartite graph | Graph coloring | Leetcode #886 • Techdose • 54,083 views views
Watch 9 more video solutions →Practice Possible Bipartition with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor