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>, // 有向辺 ruv: Vec>, // 有向グラフの逆辺 used: Vec, // 探索済み頂点 orders: Vec, // 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>) { 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>{ // 有向辺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;