Submission #73708534

---

Source Code Expand

use proconio::input;

const MOD: usize = 998244353;

fn main() {
    input! { n: usize, m: usize }

    let mut edges = Vec::with_capacity(m);
    for _ in 0..m {
        input! { u: usize, v: usize }
        edges.push((u - 1, v - 1));
    }

    let mut pow2 = vec![0usize; m + 1];
    pow2[0] = 1;
    for i in 1..=m {
        pow2[i] = (pow2[i - 1] * 2) % MOD;
    }

    let mut dsu = ac_library::Dsu::new(n);
    let mut removed_cost_sum = 0usize;
    let mut component_count = n;

    for i in (0..m).rev() {
        let (u, v) = edges[i];
        let edge_index = i + 1;

        if !dsu.same(u, v) {
            if component_count > 2 {
                dsu.merge(u, v);
                component_count -= 1;
            } else {
                removed_cost_sum = (removed_cost_sum + pow2[edge_index]) % MOD;
            }
        }
    }

    println!("{}", removed_cost_sum);
}

Submission Info

Judge Result