結果

問題 No.2780 The Bottle Imp
ユーザー NakLon131
提出日時 2024-06-12 22:42:44
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 3,368 bytes
コンパイル時間 15,080 ms
コンパイル使用メモリ 379,288 KB
実行使用メモリ 31,616 KB
最終ジャッジ日時 2024-06-12 22:43:04
合計ジャッジ時間 17,203 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

fn main() {
    input!{
        n: usize,
    }
    // 強連結成分分解
    let mut scc = Sccgh::new(n);
    for from in 1..=n {
        input!{
            m: usize,
        }
        if m == 0 { continue; }
        input!{
            a: [usize; m],
        }
        for &to in &a {
            // 辺を追加
            scc.add_edge(from-1, to-1);
        }
    }
    // 強連結成分分解を実施
    let scc_info = scc.get_component();
    // 各頂点を連結成分のグループに割り当て
    let mut groups = vec![0; n];
    for i in 0..scc_info.len() {
        for &s in &scc_info[i] {
            groups[s] = i;
        }
    }
    // 頂点0からトポロジカル順に全てたどれるか判定
    if groups[0] != 0 {
        println!("No");
        return;
    }
    for i in 0..scc_info.len()-1 {
        let mut f = false;
        // 各連結成分の頂点
        for &from in &scc_info[i] {
            for &to in &scc.uv[from] {
                if groups[from] + 1 == groups[to] { f = true;}
            }
        }
        if !f { println!("No"); return; }
    }
    println!("Yes");
}
struct Sccgh {
    n: usize, // グラフサイズ
    uv: Vec<Vec<usize>>, // 有向辺
    ruv: Vec<Vec<usize>>, // 有向グラフの逆辺
    used: Vec<bool>, // 探索済み頂点
    orders: Vec<usize>, // DFSの帰りがけ頂点
}
impl Sccgh {
    // 初期化
    pub fn new(n: usize) -> Self {
        let uv = vec![vec![0; 0]; n];
        let ruv = vec![vec![0; 0]; n];
        let used = vec![false; n];
        let orders = vec![0; 0];
        // let component  = vec![vec![0; 0]; n];
        Sccgh {n, uv, ruv, used, orders}
    }
    // 有向辺と逆の有向辺を追加
    pub fn add_edge(&mut self, x: usize, y: usize) {
        self.uv[x].push(y);
        self.ruv[y].push(x);
    }
    // 有向辺DFSして帰りがけに頂点を記録
    fn dfs(&mut self, cpos: usize){
        self.used[cpos] = true;
        let neighbors = self.uv[cpos].clone();
        for &npos in &neighbors {
            if self.used[npos] { continue; }
            self.dfs(npos);
        }
        self.orders.push(cpos);
    }
    // 記録した頂点と逆順に逆辺有向辺DFS
    fn rdfs(&mut self, cpos: usize, group_num: usize, component: &mut Vec<Vec<usize>>) {
        self.used[cpos] = true;
        component[group_num].push(cpos);
        let neighbors = self.ruv[cpos].clone();
        for &npos in &neighbors {
            if self.used[npos] { continue; }
            self.rdfs(npos, group_num, component);
        }
    }
    // 強連結成分分解を実行
    // 連結成分リストを返す
    // 得られる情報
    // 1.連結成分分解の個数と要素。自己ループ、閉路、隣の頂点のいずれか
    // 2.連結成分分解はトポロジカル順である。
    fn get_component(&mut self) -> Vec<Vec<usize>>{
        // 有向辺DFSして帰りがけに頂点を記録
        self.used = vec![false; self.n];
        for pos in 0..self.n {
            if self.used[pos] { continue; }
            self.dfs(pos);
        }
                
        let mut cnt = 0;
        self.used = vec![false; self.n];
        let mut component  = Vec::new();
        // 記録した頂点と逆順に逆辺有向辺DFS
        let mut serach = self.orders.clone();
        serach.reverse();
        for &pos in &serach {
            if self.used[pos] { continue; }
            component.push(Vec::new());
            self.rdfs(pos, cnt, &mut component);
            cnt += 1;
        }
        component
    }
}
use::proconio::input;
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0