Building Teams

warning: unused import: `std::cmp::min`
 --> input/code.rs:1:5
  |
1 | use std::cmp::min;
  |     ^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unnecessary parentheses around `while` condition
  --> input/code.rs:66:11
   |
66 |     while (!q.is_empty()) {
   |           ^             ^
   |
   = note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
   |
66 -     while (!q.is_empty()) {
66 +     while !q.is_empty() {
   |

warning: 2 warnings emitted

use std::cmp::min;
use std::collections::VecDeque;
use std::io::{self, Read};

macro_rules! input {
    ($it: expr) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: expr, $T: ty) => {
        $it.next().unwrap().parse::<$T>().unwrap()
    };
}
/*
mod classes;
fn main() {
    // println!("{}", "-".repeat(20));
    classes::c03::task1();
    // println!("{}", "-".repeat(20));
}
// */

fn main() {
    task();
}

#[allow(dead_code)]
fn task() {
    let mut buf = String::new();
    io::stdin().read_to_string(&mut buf).unwrap();

    let mut it = buf.split_whitespace();

    let (n, m): (usize, usize) = (input!(it), input!(it));

    let mut g:Vec<Vec<usize>> = vec![vec![]; n+1];

    for _ in 1..m+1 {
        let (v, u): (usize, usize) = (input!(it), input!(it));
        g[v].push(u);
        g[u].push(v);
    }

    let mut q = VecDeque::new();
    let mut visited = vec![false; n+1];
    let mut color: Vec<usize> = vec![0; n+1];
    let mut valid = true;

    for x in 1..n+1 {
        if visited[x] == false {
            visited[x] = true;
            color[x] = 1;
            q.push_back(x);
            valid = valid && bfs(&mut q, &mut visited, &mut color, &g);
        }
    }

    if valid {
        for i in 1..n+1 {
            print!("{} ", color[i]);
        }
    } else { println!("IMPOSSIBLE") }
}

// Implementation from the book, page n. 120 (130)
pub fn bfs(q: &mut VecDeque<usize>, visited: &mut Vec<bool>, color: &mut Vec<usize>, g: &Vec<Vec<usize>>) -> bool {
    while (!q.is_empty()) {
        let s = q.pop_front().unwrap();
        // process node s
        for &u in &g[s] {
            if !(visited[u]){
                visited[u] = true;
                color[u] = 3-color[s];
                q.push_back(u);
            } else if color[u] == color[s] {
                return false;
            }
        }
    }
    true
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED