use proconio::input; fn main() { input!{ n: usize, } // 有向辺と逆辺 let mut uv = vec![Vec::new(); n]; let mut ruv = vec![Vec::new(); n]; for from in 1..=n { input!{ m: usize, } if m == 0 { continue; } input!{ a: [usize; m], } for to in a { uv[from-1].push(to-1); ruv[to-1].push(from-1); } } // -- 強連結成分分解 -- // 有向辺DFSして帰りがけに頂点を記録 fn dfs(spos: usize, uv: &Vec>, n: usize, used: &mut Vec, orders: &mut Vec){ used[spos] = true; for &npos in &uv[spos] { if used[npos] { continue; } dfs(npos, uv, n, used, orders); } orders.push(spos); } let mut used = vec![false; n]; let mut orders = Vec::new(); for i in 0..n { if used[i] { continue; } dfs(i, &uv, n, &mut used, &mut orders); } // 記録した頂点と逆順に逆辺有向辺DFS fn rdfs(spos: usize, ruv: &Vec>, n: usize, used: &mut Vec, compo: &mut Vec>, cnt: usize) { used[spos] = true; compo[cnt].push(spos); for &npos in &ruv[spos] { if used[npos] { continue; } rdfs(npos, ruv, n, used, compo, cnt); } } let mut compo_cnt = 0; let mut used = vec![false; n]; let mut compo = Vec::new(); orders.reverse(); for &i in &orders { if used[i] { continue; } compo.push(Vec::new()); rdfs(i, &ruv, n, &mut used, &mut compo, compo_cnt); compo_cnt += 1; } // -- 強連結成分分解 -- // 各頂点を連結成分のグループに割り当て let mut compo_group = vec![0; n]; for i in 0..compo.len() { for &c in &compo[i] { compo_group[c] = i; } } // 初めの連結成分が0でない場合は、No if compo_group[0] != 0 { println!("No"); return; } // 連結成分を順番に辿る // 辿ることができない連結成分があったらNo for i in 0..compo.len()-1 { let mut f = false; // 各連結成分の頂点 for &from in &compo[i] { // 各連結成分にある有向辺 for &to in &uv[from] { // k->l について、連結成分が連番であればよい。 if compo_group[from] + 1 == compo_group[to] { f = true; } } } if !f { println!("No"); return; } } println!("Yes"); }