#1159574 (Rust) No.3508 OR Mapping

• 問題: No.3508 OR Mapping
• ユーザー: ガルム
• 提出日時: 2026-04-18 13:40:55
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 324 ms / 2,000 ms
• コード長: 4,247 bytes
• コンパイル時間: 3,974 ms
• コンパイル使用メモリ: 195,540 KB
• 実行使用メモリ: 103,104 KB
• 最終ジャッジ日時: 2026-04-18 13:41:17
• 合計ジャッジ時間: 15,914 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

ファイルパターン	結果
sample	AC * 2
other	AC * 65

ソースコード

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

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut it = input.split_whitespace().map(|x| x.parse::<usize>().unwrap());

    let n = it.next().unwrap();
    let m = it.next().unwrap();
    let _k = it.next().unwrap();

    let mut graph = vec![Vec::<usize>::new(); n];
    let mut rev_graph = vec![Vec::<usize>::new(); n];
    let mut edges = Vec::with_capacity(m);

    for _ in 0..m {
        let u = it.next().unwrap() - 1;
        let v = it.next().unwrap() - 1;
        graph[u].push(v);
        rev_graph[v].push(u);
        edges.push((u, v));
    }

    let mut seen = vec![false; n];
    let mut order = Vec::with_capacity(n);

    for start in 0..n {
        if seen[start] {
            continue;
        }

        seen[start] = true;
        let mut stack = vec![(start, 0_usize)];
        while let Some((v, idx)) = stack.last_mut() {
            if *idx < graph[*v].len() {
                let to = graph[*v][*idx];
                *idx += 1;
                if !seen[to] {
                    seen[to] = true;
                    stack.push((to, 0));
                }
            } else {
                order.push(*v);
                stack.pop();
            }
        }
    }

    let mut comp = vec![usize::MAX; n];
    let mut comp_count = 0_usize;

    for &start in order.iter().rev() {
        if comp[start] != usize::MAX {
            continue;
        }

        comp[start] = comp_count;
        let mut stack = vec![start];
        while let Some(v) = stack.pop() {
            for &to in &rev_graph[v] {
                if comp[to] == usize::MAX {
                    comp[to] = comp_count;
                    stack.push(to);
                }
            }
        }
        comp_count += 1;
    }

    let mut comp_size = vec![0_usize; comp_count];
    for &c in &comp {
        comp_size[c] += 1;
    }

    let mut has_odd_cycle = vec![false; comp_count];
    let mut color = vec![usize::MAX; n];

    for start in 0..n {
        if color[start] != usize::MAX {
            continue;
        }

        color[start] = 0;
        let mut stack = vec![start];
        while let Some(v) = stack.pop() {
            for &to in &graph[v] {
                if comp[v] != comp[to] {
                    continue;
                }

                let expected = color[v] ^ 1;
                if color[to] == usize::MAX {
                    color[to] = expected;
                    stack.push(to);
                } else if color[to] != expected {
                    has_odd_cycle[comp[v]] = true;
                }
            }
        }
    }

    let start_comp = comp[0];
    if comp_size[start_comp] == 1 {
        println!("No");
        return;
    }

    for c in 0..comp_count {
        if comp_size[c] > 1 && !has_odd_cycle[c] {
            println!("No");
            return;
        }
    }

    let mut comp_edges = Vec::new();
    for &(u, v) in &edges {
        let cu = comp[u];
        let cv = comp[v];
        if cu != cv {
            comp_edges.push((cu, cv));
        }
    }
    comp_edges.sort_unstable();
    comp_edges.dedup();

    let mut dag = vec![Vec::<usize>::new(); comp_count];
    let mut indeg = vec![0_usize; comp_count];
    for &(u, v) in &comp_edges {
        dag[u].push(v);
        indeg[v] += 1;
    }

    let mut que = VecDeque::new();
    for c in 0..comp_count {
        if indeg[c] == 0 {
            que.push_back(c);
        }
    }

    let mut topo = Vec::with_capacity(comp_count);
    while let Some(v) = que.pop_front() {
        topo.push(v);
        for &to in &dag[v] {
            indeg[to] -= 1;
            if indeg[to] == 0 {
                que.push_back(to);
            }
        }
    }

    if topo.len() != comp_count || topo[0] != start_comp {
        println!("No");
        return;
    }

    for i in 0..topo.len().saturating_sub(1) {
        if comp_edges.binary_search(&(topo[i], topo[i + 1])).is_err() {
            println!("No");
            return;
        }
        if comp_size[topo[i]] == 1 && comp_size[topo[i + 1]] == 1 {
            println!("No");
            return;
        }
    }

    println!("Yes");
}