#![allow(non_snake_case, unused_imports)] use proconio::{fastout, input, marker::*}; #[fastout] fn main() { input! { N: usize, } let mut edges = vec![]; for i in 0..N { input! { M: usize, A: [Usize1; M], } for a in A { edges.push((i, a)); } } let scc = strongly_connected_components(N, &edges); let (z, zi) = coordinate_compression(&scc); let n = z.len(); let mut edges_set = std::collections::HashSet::new(); let mut deg_out = vec![0; n]; let mut deg_in = vec![0; N]; for (u, v) in edges { if scc[u] == scc[v] { continue; } edges_set.insert((*zi.get(&scc[u]).unwrap(), *zi.get(&scc[v]).unwrap())); deg_out[*zi.get(&scc[u]).unwrap()] += 1; deg_in[*zi.get(&scc[v]).unwrap()] += 1; } let ord = topological_sort( n, &edges_set.iter().map(|&(u, v)| (u, v)).collect::>(), ); let s = *zi.get(&scc[0]).unwrap(); if ord[s] != 0 { println!("No"); return; } // eprintln!( // "scc: {}", // scc.iter() // .map(|x| x.to_string()) // .collect::>() // .join(" ") // ); // eprintln!( // "ord: {}", // ord.iter() // .map(|x| x.to_string()) // .collect::>() // .join(" ") // ); for i in 0..n - 1 { if deg_out[ord[i]] == 0 { println!("No"); return; } } for i in 1..n { if deg_in[ord[i]] == 0 { println!("No"); return; } } println!("Yes"); } fn coordinate_compression( values: &[T], ) -> (Vec, std::collections::BTreeMap) { let s: std::collections::BTreeSet = values.iter().cloned().collect(); let z: Vec = s.iter().cloned().collect(); let zinv: std::collections::BTreeMap = z.iter().enumerate().map(|(i, &v)| (v, i)).collect(); (z, zinv) } fn topological_sort(N: usize, E: &[(usize, usize)]) -> Vec { let mut graph = vec![vec![]; N]; let mut out_degree = vec![0; N]; let mut ord = vec![]; for &(u, v) in E { graph[v].push(u); out_degree[u] += 1; } for i in 0..N { graph[i].sort(); } let mut q = std::collections::VecDeque::new(); for i in 0..N { if out_degree[i] == 0 { q.push_back(i); } } while let Some(now) = q.pop_front() { ord.push(now); for &nxt in graph[now].iter() { out_degree[nxt] -= 1; if out_degree[nxt] == 0 { q.push_back(nxt); } } } ord.reverse(); return ord; } fn strongly_connected_components(N: usize, E: &Vec<(usize, usize)>) -> Vec { struct Graph { list: Vec>, seen: Vec, stop: Vec, } impl Graph { fn dfs(&mut self, now: usize) { self.seen[now] = true; for &nxt in self.list[now].clone().iter() { if self.seen[nxt] { continue; } self.dfs(nxt); } self.stop.push(now); } } let mut g = vec![vec![]; N]; let mut g_inv = vec![vec![]; N]; for &(u, v) in E.iter() { g[u].push(v); g_inv[v].push(u); } let mut G = Graph { list: g, seen: vec![false; N], stop: vec![], }; for i in 0..N { if !G.seen[i] { G.dfs(i); } } let mut stop = G.stop; stop.reverse(); let mut G_inv = Graph { list: g_inv, seen: vec![false; N], stop: vec![], }; let mut ret = vec![0; N]; let mut cnt = 0; for i in stop { if !G_inv.seen[i] { G_inv.dfs(i); for &v in G_inv.stop.iter() { ret[v] = cnt; } G_inv.stop = vec![]; cnt += 1; } } return ret; }