Depth-First Search
Breadth-First Search
Union Find
Graph
Description
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 <= 2000
0 <= dislikes.length <= 104
dislikes[i].length == 2
1 <= ai < bi <= n
All the pairs of dislikes
are unique .
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution :
def possibleBipartition ( self , n : int , dislikes : List [ List [ int ]]) -> bool :
def dfs ( i , c ):
color [ i ] = c
for j in g [ i ]:
if color [ j ] == c :
return False
if color [ j ] == 0 and not dfs ( j , 3 - c ):
return False
return True
g = defaultdict ( list )
color = [ 0 ] * n
for a , b in dislikes :
a , b = a - 1 , b - 1
g [ a ] . append ( b )
g [ b ] . append ( a )
return all ( c or dfs ( i , 1 ) for i , c in enumerate ( color ))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 class Solution {
private List < Integer >[] g ;
private int [] color ;
public boolean possibleBipartition ( int n , int [][] dislikes ) {
g = new List [ n ] ;
color = new int [ n ] ;
Arrays . setAll ( g , k -> new ArrayList <> ());
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 ) {
if ( color [ i ] == 0 ) {
if ( ! dfs ( i , 1 )) {
return false ;
}
}
}
return true ;
}
private boolean dfs ( int i , int c ) {
color [ i ] = c ;
for ( int j : g [ i ] ) {
if ( color [ j ] == c ) {
return false ;
}
if ( color [ j ] == 0 && ! dfs ( j , 3 - c )) {
return false ;
}
}
return true ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 class Solution {
public :
bool possibleBipartition ( int n , vector < vector < int >>& dislikes ) {
unordered_map < int , vector < int >> g ;
for ( auto & e : dislikes ) {
int a = e [ 0 ] - 1 , b = e [ 1 ] - 1 ;
g [ a ]. push_back ( b );
g [ b ]. push_back ( a );
}
vector < int > color ( n );
function < bool ( int , int ) > dfs = [ & ]( int i , int c ) -> bool {
color [ i ] = c ;
for ( int j : g [ i ]) {
if ( ! color [ j ] && ! dfs ( j , 3 - c )) return false ;
if ( color [ j ] == c ) return false ;
}
return true ;
};
for ( int i = 0 ; i < n ; ++ i ) {
if ( ! color [ i ] && ! dfs ( i , 1 )) return false ;
}
return true ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 func possibleBipartition ( n int , dislikes [][] int ) bool {
g := make ([][] int , n )
for _ , e := range dislikes {
a , b := e [ 0 ] - 1 , e [ 1 ] - 1
g [ a ] = append ( g [ a ], b )
g [ b ] = append ( g [ b ], a )
}
color := make ([] int , n )
var dfs func ( int , int ) bool
dfs = func ( i , c int ) bool {
color [ i ] = c
for _ , j := range g [ i ] {
if color [ j ] == c {
return false
}
if color [ j ] == 0 && ! dfs ( j , 3 - c ) {
return false
}
}
return true
}
for i , c := range color {
if c == 0 && ! dfs ( i , 1 ) {
return false
}
}
return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 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 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 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
}
}
Solution 2
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 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 ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 class Solution {
public :
bool possibleBipartition ( int n , vector < vector < int >>& dislikes ) {
vector < int > p ( n );
iota ( p . begin (), p . end (), 0 );
unordered_map < int , vector < int >> g ;
for ( auto & e : dislikes ) {
int a = e [ 0 ] - 1 , b = e [ 1 ] - 1 ;
g [ a ]. push_back ( b );
g [ b ]. push_back ( a );
}
function < int ( int ) > find = [ & ]( int x ) -> int {
if ( p [ x ] != x ) p [ x ] = find ( p [ x ]);
return p [ x ];
};
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 ][ 0 ]);
}
}
return true ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 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
}
GitHub