結果

問題 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;
0