#include #define PROBLEM "https://yukicoder.me/problems/no/2780" #include #include #include #include #include #include #include #include #include #include namespace mtd { template class Graph { using Edge = std::pair; using Edges = std::vector; const int m_n; std::vector m_graph; public: Graph(int n) : m_n(n), m_graph(n) {} Graph(const std::vector& edges) : m_n(edges.size()), m_graph(edges) {} auto addEdge(const Node& f, const Node& t, const Cost& c = 1) { m_graph[f].emplace_back(t, c); } auto addEdgeUndirected(const Node& f, const Node& t, const Cost& c = 1) { addEdge(f, t, c); addEdge(t, f, c); } auto getEdges(const Node& from) const { class EdgesRange { const typename Edges::const_iterator b, e; public: EdgesRange(const Edges& edges) : b(edges.begin()), e(edges.end()) {} auto begin() const { return b; } auto end() const { return e; } }; return EdgesRange(m_graph[from]); } auto getEdges() const { std::deque> edges; for (Node from : std::views::iota(0, m_n)) { for (const auto& [to, c] : getEdges(from)) { edges.emplace_back(from, to, c); } } return edges; } auto getEdgesExcludeCost() const { std::deque> edges; for (Node from : std::views::iota(0, m_n)) { for (const auto& [to, _] : getEdges(from)) { edges.emplace_back(from, to); } } return edges; } auto reverse() const { auto rev = Graph(m_n); for (const auto& [from, to, c] : getEdges()) { rev.addEdge(to, from, c); } return rev; } auto size() const { return m_n; }; auto debug(bool directed = false) const { for (const auto& [f, t, c] : getEdges()) { if (f < t || directed) { std::cout << f << " -> " << t << ": " << c << std::endl; } } } };} namespace mtd { namespace util { template constexpr auto tuple_transform(F&& f, T&& t) { return std::apply( [&](Ts&&... elems) { return std::tuple...>( std::invoke(f, std::forward(elems))...); }, std::forward(t)); } template constexpr auto tuple_for_each(F&& f, T&& t) { std::apply( [&](Ts&&... elems) { (std::invoke(f, std::forward(elems)), ...); }, std::forward(t)); } } } namespace mtd { template class StronglyConnectedComponents { struct HashPair { template size_t operator()(const std::pair& p) const { auto hash1 = std::hash{}(p.first); auto hash2 = std::hash{}(p.second); size_t seed = 0; seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2); seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2); return seed; } }; const Graph m_graph; const std::vector m_group; template constexpr static inline auto dfs(const Graph& graph, int from, std::vector& is_used, const F& f) -> void { is_used[from] = true; for (const auto& [to, _] : graph.getEdges(from)) { if (is_used[to]) { continue; } dfs(graph, to, is_used, f); } f(from); } constexpr static auto constructGroup(const Graph& graph) { int n = graph.size(); std::vector order; std::vector is_used(n); for (auto from : std::views::iota(0, n)) { if (is_used[from]) { continue; } dfs(graph, from, is_used, [&](int f) { order.emplace_back(f); }); } int g = 0; std::vector group(n); std::vector is_used2(n); auto rev = graph.reverse(); for (auto from : order | std::views::reverse) { if (is_used2[from]) { continue; } dfs(rev, from, is_used2, [&](int f) { group[f] = g; }); ++g; } return group; } public: [[deprecated]] constexpr StronglyConnectedComponents( const Graph& graph) : m_graph(graph), m_group(constructGroup(m_graph)) {} constexpr StronglyConnectedComponents(Graph&& graph) : m_graph(std::move(graph)), m_group(constructGroup(m_graph)) {} constexpr auto size() const { return *std::max_element(m_group.begin(), m_group.end()) + 1; } constexpr auto group(int a) const { return m_group[a]; } constexpr auto isSameGroup(int a, int b) const { return m_group[a] == m_group[b]; } constexpr auto getGroupNodes() const { std::vector> groupNodes(size()); for (int gi = 0; gi < m_graph.size(); ++gi) { groupNodes[m_group[gi]].emplace_back(gi); } return groupNodes; } constexpr auto getGroupGraph() const { std::unordered_set, HashPair> st; st.reserve(m_graph.size()); for (int f = 0; f < m_graph.size(); ++f) { for (const auto& [t, _] : m_graph.getEdges(f)) { if (!isSameGroup(f, t)) { st.emplace(m_group[f], m_group[t]); } } } Graph ret(size()); for (const auto& [f, t] : st) { ret.addEdge(f, t); } return ret; } };} namespace mtd { namespace ranges { namespace __detail { template concept __all_random_access = (std::ranges::random_access_range && ...); template concept __all_bidirectional = (std::ranges::bidirectional_range && ...); template concept __all_forward = (std::ranges::forward_range && ...); template constexpr auto _S_iter_concept() { if constexpr (__all_random_access) { return std::random_access_iterator_tag{}; } else if constexpr (__all_bidirectional) { return std::bidirectional_iterator_tag{}; } else if constexpr (__all_forward) { return std::forward_iterator_tag{}; } else { return std::input_iterator_tag{}; } } } template struct zip_view : public std::ranges::view_interface> { class iterator { public: std::tuple...> _M_current; using difference_type = int; using value_type = std::tuple< std::iter_reference_t>...>; using iterator_concept = decltype(__detail::_S_iter_concept<_Range...>()); constexpr iterator() = default; constexpr explicit iterator(const decltype(_M_current)& __current) : _M_current(__current) {} constexpr auto operator*() const { return util::tuple_transform([](auto& __i) { return *__i; }, _M_current); } constexpr auto& operator++() { util::tuple_for_each([](auto& __i) { ++__i; }, _M_current); return *this; } constexpr auto operator++(int) { return ++*this; } constexpr auto operator==(const iterator& other) const { return [&](std::index_sequence<_Is...>) { return ((std::get<_Is>(_M_current) == std::get<_Is>(other._M_current)) || ...); } (std::make_index_sequence{}); } constexpr auto& operator--() requires __detail::__all_bidirectional<_Range...> { util::tuple_for_each([](auto& __i) { --__i; }, _M_current); return *this; } constexpr auto operator--( int) requires __detail::__all_bidirectional<_Range...> { return --*this; } constexpr auto operator<=>(const iterator&) const requires __detail::__all_random_access<_Range...> = default; constexpr auto operator-(const iterator& itr) const requires __detail::__all_random_access<_Range...> { return [&](std::index_sequence<_Is...>) { return std::ranges::min({difference_type( std::get<_Is>(_M_current) - std::get<_Is>(itr._M_current))...}); } (std::make_index_sequence{}); } constexpr auto& operator+=(const difference_type n) requires __detail::__all_random_access<_Range...> { util::tuple_for_each([&n](auto& __i) { __i += n; }, _M_current); return *this; } constexpr auto operator+(const difference_type n) const requires __detail::__all_random_access<_Range...> { auto __r = *this; __r += n; return __r; } constexpr friend auto operator+(const difference_type n, const iterator& itr) requires __detail::__all_random_access<_Range...> { return itr + n; } constexpr auto& operator-=(const difference_type n) requires __detail::__all_random_access<_Range...> { util::tuple_for_each([&n](auto& __i) { __i -= n; }, _M_current); return *this; } constexpr auto operator-(const difference_type n) const requires __detail::__all_random_access<_Range...> { auto __r = *this; __r -= n; return __r; } constexpr auto operator[](const difference_type n) const requires __detail::__all_random_access<_Range...> { return util::tuple_transform([&n](auto& __i) { return __i[n]; }, _M_current); } }; class sentinel { public: std::tuple...> _M_end; constexpr sentinel() = default; constexpr explicit sentinel(const decltype(_M_end)& __end) : _M_end(__end) {} friend constexpr bool operator==(const iterator& __x, const sentinel& __y) { return [&](std::index_sequence<_Is...>) { return ( (std::get<_Is>(__x._M_current) == std::get<_Is>(__y._M_end)) || ...); } (std::make_index_sequence{}); } }; std::tuple<_Range...> __r; constexpr explicit zip_view(const _Range&... __r) : __r(__r...) {} constexpr auto begin() { return iterator(util::tuple_transform(std::ranges::begin, __r)); } constexpr auto end() { return sentinel(util::tuple_transform(std::ranges::end, __r)); } }; namespace __detail { template auto _flatten(const T& t) { return std::make_tuple(t); } template auto _flatten(const std::tuple& t); template auto _flatten_impl(const Head& head, const Tail&... tail) { return std::tuple_cat(_flatten(head), _flatten(tail)...); } template auto _flatten(const std::tuple& t) { return std::apply( [](const auto&... args) { return _flatten_impl(args...); }, t); } } template struct flatten_view : public std::ranges::view_interface> { class iterator { public: std::ranges::iterator_t<_Range> _M_current; using difference_type = std::ranges::range_difference_t<_Range>; using value_type = decltype(__detail::_flatten( std::declval< std::iter_reference_t>>())); using iterator_concept = decltype(__detail::_S_iter_concept<_Range>()); constexpr iterator() = default; constexpr explicit iterator(decltype(_M_current) __current) : _M_current(__current) {} constexpr auto operator*() const { return __detail::_flatten(*_M_current); } constexpr auto& operator++() { ++_M_current; return *this; } constexpr auto operator++(int) { return ++*this; } constexpr auto operator==(const iterator& other) const { return _M_current == other._M_current; } constexpr auto& operator--() requires __detail::__all_bidirectional<_Range> { --_M_current; return *this; } constexpr auto operator--( int) requires __detail::__all_bidirectional<_Range> { return --*this; } constexpr auto operator<=>(const iterator&) const requires __detail::__all_random_access<_Range> = default; constexpr auto operator-(const iterator& itr) const requires __detail::__all_random_access<_Range> { return _M_current - itr._M_current; } constexpr auto& operator+=(const difference_type n) requires __detail::__all_random_access<_Range> { _M_current += n; return *this; } constexpr auto operator+(const difference_type n) const requires __detail::__all_random_access<_Range> { auto __r = *this; __r += n; return __r; } constexpr friend auto operator+(const difference_type n, const iterator& itr) requires __detail::__all_random_access<_Range> { return itr + n; } constexpr auto& operator-=(const difference_type n) requires __detail::__all_random_access<_Range> { _M_current -= n; return *this; } constexpr auto operator-(const difference_type n) const requires __detail::__all_random_access<_Range> { auto __r = *this; __r -= n; return __r; } constexpr auto operator[](const difference_type n) const requires __detail::__all_random_access<_Range> { return __detail::_flatten(_M_current[n]); } }; class sentinel { std::ranges::sentinel_t<_Range> _M_end; public: constexpr sentinel() = default; constexpr explicit sentinel(const decltype(_M_end)& __end) : _M_end(__end) {} friend constexpr bool operator==(const iterator& __x, const sentinel& __y) { return __x._M_current == __y._M_end; } }; _Range __r; constexpr explicit flatten_view(const _Range& __r) : __r(__r) {} constexpr auto begin() { return iterator(std::ranges::begin(__r)); } constexpr auto end() { return sentinel(std::ranges::end(__r)); } }; } namespace views { namespace __detail { template concept __can_zip_view = requires { ranges::zip_view(std::declval<_Args>()...); }; template concept __can_flatten_view = requires { ranges::flatten_view(std::declval<_Args>()...); }; } struct _ZipView { template requires __detail::__can_zip_view<_Tp...> constexpr auto operator() [[nodiscard]] (_Tp&&... __e) const { return ranges::zip_view(std::forward<_Tp>(__e)...); } }; struct _Enumerate : std::views::__adaptor::_RangeAdaptorClosure { template requires __detail::__can_zip_view, _Tp> constexpr auto operator() [[nodiscard]] (_Tp&& __e) const { return ranges::zip_view{std::views::iota(0), std::forward<_Tp>(__e)}; } static constexpr bool _S_has_simple_call_op = true; }; struct _Flatten : std::views::__adaptor::_RangeAdaptorClosure { template requires __detail::__can_flatten_view<_Tp...> constexpr auto operator() [[nodiscard]] (_Tp&&... __e) const { return ranges::flatten_view(std::forward<_Tp>(__e)...); } static constexpr bool _S_has_simple_call_op = true; }; inline constexpr _ZipView zip{}; inline constexpr _Enumerate enumerate{}; inline constexpr _Flatten flatten{}; } } namespace mtd { template auto topological_order(const mtd::Graph& graph) { std::vector cnt(graph.size()); for (auto [_, v] : graph.getEdgesExcludeCost()) { ++cnt[v]; } std::deque q; for (auto [nd, c] : cnt | mtd::views::enumerate) { if (c == 0) { q.emplace_back(nd); } } std::vector order; while (!q.empty()) { auto nd = q.front(); q.pop_front(); order.emplace_back(nd); for (auto [v, _] : graph.getEdges(nd)) { --cnt[v]; if (cnt[v] == 0) { q.emplace_back(v); } } } return order; }} int main() { std::cin.tie(0); std::ios::sync_with_stdio(0); int n; std::cin >> n; auto graph = mtd::Graph<>(n); for (auto u : std::views::iota(0, n)) { int m; std::cin >> m; for ([[maybe_unused]] auto _ : std::views::iota(0, m)) { int v; std::cin >> v; graph.addEdge(u, v - 1); } } auto scc = mtd::StronglyConnectedComponents(std::move(graph)); auto scc_graph = scc.getGroupGraph(); auto size = scc.size(); std::vector dp(size); dp[scc.group(0)] = true; for (auto u : mtd::topological_order(scc_graph)) { for (auto [v, _] : scc_graph.getEdges(u)) { dp[v] |= dp[u]; } } auto yes = std::ranges::all_of(dp, [](int x) { return x; }); std::cout << (yes ? "Yes" : "No") << std::endl; }