結果

問題 No.2780 The Bottle Imp
ユーザー NakLon131NakLon131
提出日時 2024-06-12 22:42:44
言語 Rust
(1.77.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 0 ms
5,376 KB
testcase_07 AC 31 ms
12,228 KB
testcase_08 AC 31 ms
12,232 KB
testcase_09 AC 33 ms
12,100 KB
testcase_10 AC 38 ms
12,228 KB
testcase_11 AC 36 ms
12,052 KB
testcase_12 AC 65 ms
22,016 KB
testcase_13 AC 64 ms
22,144 KB
testcase_14 AC 16 ms
7,040 KB
testcase_15 AC 17 ms
7,040 KB
testcase_16 AC 17 ms
7,040 KB
testcase_17 AC 17 ms
7,040 KB
testcase_18 AC 16 ms
6,912 KB
testcase_19 AC 16 ms
7,040 KB
testcase_20 AC 16 ms
7,040 KB
testcase_21 AC 16 ms
6,944 KB
testcase_22 AC 12 ms
5,888 KB
testcase_23 AC 15 ms
6,528 KB
testcase_24 AC 26 ms
10,496 KB
testcase_25 AC 50 ms
16,512 KB
testcase_26 AC 22 ms
8,960 KB
testcase_27 AC 18 ms
9,864 KB
testcase_28 AC 18 ms
9,864 KB
testcase_29 AC 22 ms
12,032 KB
testcase_30 AC 16 ms
9,984 KB
testcase_31 AC 39 ms
18,176 KB
testcase_32 AC 8 ms
5,504 KB
testcase_33 AC 54 ms
30,080 KB
testcase_34 AC 59 ms
31,616 KB
testcase_35 AC 6 ms
5,376 KB
testcase_36 AC 1 ms
5,376 KB
testcase_37 AC 1 ms
5,376 KB
testcase_38 AC 6 ms
5,376 KB
testcase_39 AC 33 ms
18,272 KB
testcase_40 AC 34 ms
18,272 KB
testcase_41 AC 36 ms
18,268 KB
testcase_42 AC 1 ms
5,376 KB
testcase_43 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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