aboutsummaryrefslogtreecommitdiff
path: root/possible_bipartition.rs
diff options
context:
space:
mode:
Diffstat (limited to 'possible_bipartition.rs')
-rw-r--r--possible_bipartition.rs40
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));
+}