bouzuya.hatenablog.com

ぼうずやのにっき

EDPC G を解いた

  • EDPC G - Longest Path (AtCoder Educational DP Contest G問題) https://atcoder.jp/contests/dp/tasks/dp_g
    • https://atcoder.jp/contests/dp/submissions/40944118
    • 頂点ごとにそこからの最長パスの長さを保持する
    • 頂点から出る辺のないものから順に、その頂点に入る辺を消していく
    • 辺を消すタイミングで、遷移元の頂点の最長パスの長さを現在の頂点のそれ +1 で最大のものに更新する
    • すべての頂点のそこからの最長パスの長さのうち最大のものが答えになる
use std::collections::{HashSet, VecDeque};

use proconio::{input, marker::Usize1};

macro_rules! chmax {
    ($max_v: expr, $v: expr) => {
        if $v > $max_v {
            $max_v = $v;
            true
        } else {
            false
        }
    };
}

fn main() {
    input! {
        n: usize,
        m: usize,
        xy: [(Usize1, Usize1); m],
    }

    let mut edges = vec![HashSet::new(); n];
    let mut redges = vec![HashSet::new(); n];
    for (x, y) in xy {
        edges[x].insert(y);
        redges[y].insert(x);
    }

    let mut deque = VecDeque::new();
    for (i, e) in edges.iter().enumerate() {
        if e.is_empty() {
            deque.push_back(i);
        }
    }
    let mut dp = vec![0_usize; n];
    while let Some(v) = deque.pop_front() {
        for u in redges[v].iter().copied() {
            chmax!(dp[u], dp[v] + 1);
            edges[u].remove(&v);
            if edges[u].is_empty() {
                deque.push_back(u);
            }
        }
    }
    let ans = dp.iter().copied().max().unwrap();
    println!("{}", ans);
}

今日のコミット。