diff options
Diffstat (limited to 'possible_bipartition.rs')
-rw-r--r-- | possible_bipartition.rs | 40 |
1 files changed, 40 insertions, 0 deletions
diff --git a/possible_bipartition.rs b/possible_bipartition.rs new file mode 100644 index 0000000..13b8cf5 --- /dev/null +++ b/possible_bipartition.rs @@ -0,0 +1,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)); +} |