aboutsummaryrefslogtreecommitdiff
path: root/possible_bipartition.rs
blob: 13b8cf51746b6ab74e2b7b2863e578846084d63b (plain)
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
37
38
39
40
use std::collections::VecDeque;
struct Solution;

impl Solution {
    pub fn possible_bipartition(n: i32, dislikes: Vec<Vec<i32>>) -> bool {
        let mut dmap: Vec<Vec<usize>> = vec![vec![]; n as usize];
        for d in dislikes.iter() {
            dmap[d[0] as usize - 1].push(d[1] as usize - 1);
            dmap[d[1] as usize - 1].push(d[0] as usize - 1);
        }
        let mut v: Vec<Option<bool>> = vec![None; n as usize];
        for i in 0..n as usize {
            if v[i].is_some() {
                continue;
            }
            let mut vd: VecDeque<(usize, bool)> = VecDeque::new();
            vd.push_back((i, true));
            while let Some(last) = vd.pop_front() {
                if let Some(b) = v[last.0] {
                    if b != last.1 {
                        return false;
                    }
                    continue;
                }
                v[last.0] = Some(last.1);
                for j in dmap[last.0].iter() {
                    if v[*j].is_none() {
                        vd.push_back((*j, !last.1));
                    }
                }
            }
        }
        true
    }
}

fn main() {
    let dislikes = vec![vec![1,2], vec![1,3], vec![2,4]];
    print!("{}", Solution::possible_bipartition(4, dislikes));
}