Test/Graph/Normal/Topological.test.cpp

• View this file on GitHub
• Last update: 2025-12-20 02:07:58+09:00
• Problem: https://yukicoder.me/problems/no/2780

Depends on

• Library/Graph/Graph.hpp
• Library/Graph/Normal/StronglyConnectedComponents.hpp
• Library/Graph/Normal/Topological.hpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/2780"
#include <iostream>

// begin:tag includes
#include "../../../Library/Graph/Normal/StronglyConnectedComponents.hpp"
#include "../../../Library/Graph/Normal/Topological.hpp"
// end:tag includes

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.addArc(u, v - 1);
    }
  }

  auto scc = mtd::StronglyConnectedComponents(std::move(graph));
  auto scc_graph = scc.getGroupGraph();
  auto scc_nodes = scc.getGroupNodes();

  int now = -1;
  bool yes = true;
  for (auto u : mtd::topological_order(scc_graph)) {
    bool ex = (now == -1 ? u == scc.group(0) : false);
    if (now > -1) {
      for (auto [v, _] : scc_graph.getEdges(now)) { ex |= (u == v); }
    }
    yes &= ex;
    now = u;
  }

  std::cout << (yes ? "Yes" : "No") << std::endl;
}

#line 1 "Test/Graph/Normal/Topological.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/2780"
#include <iostream>

// begin:tag includes
#line 2 "Library/Graph/Normal/StronglyConnectedComponents.hpp"

#include <algorithm>

#include <concepts>

#include <ranges>

#include <set>

#include <unordered_set>

#include <vector>


#line 2 "Library/Graph/Graph.hpp"
#include <deque>

#line 5 "Library/Graph/Graph.hpp"
#include <tuple>

#line 7 "Library/Graph/Graph.hpp"

namespace mtd {
  template <class Node = long long, class Cost = long long>
  class Graph {
    using Edge = std::pair<Node, Cost>;
    using Edges = std::vector<Edge>;

    const int m_n;
    std::vector<Edges> m_graph;

  public:
    Graph(int n) : m_n(n), m_graph(n) {}
    Graph(const std::vector<Edges>& edges)
        : m_n(edges.size()), m_graph(edges) {}
    Graph(int n, const std::vector<std::tuple<Node, Node>>& edges,
          bool is_arc = false, bool is_index1 = true)
        : Graph<Node, Cost>(n) {
      for (auto [u, v] : edges) {
        u -= is_index1;
        v -= is_index1;
        if (is_arc) {
          addArc(u, v);
        } else {
          addEdge(u, v);
        }
      }
    }
    Graph(int n, const std::vector<std::tuple<Node, Node, Cost>>& edges,
          bool is_arc = false, bool is_index1 = true)
        : Graph<Node, Cost>(n) {
      for (auto [u, v, c] : edges) {
        u -= is_index1;
        v -= is_index1;
        if (is_arc) {
          addArc(u, v, c);
        } else {
          addEdge(u, v, c);
        }
      }
    }

    auto addEdge(const Node& f, const Node& t, const Cost& c = 1) {
      addArc(f, t, c);
      addArc(t, f, c);
    }
    auto addArc(const Node& f, const Node& t, const Cost& c = 1) {
      m_graph[f].emplace_back(t, 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<std::tuple<Node, Node, Cost>> 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<std::pair<Node, Node>> 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<Node, Cost>(m_n);
      for (const auto& [from, to, c] : getEdges()) { rev.addArc(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

#line 11 "Library/Graph/Normal/StronglyConnectedComponents.hpp"

namespace mtd {
  template <class Node, class Cost>
  class StronglyConnectedComponents {
    struct HashPair {
      template <class T1, class T2>
      size_t operator()(const std::pair<T1, T2>& p) const {
        auto hash1 = std::hash<T1>{}(p.first);
        auto hash2 = std::hash<T2>{}(p.second);
        size_t seed = 0;
        seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
      }
    };

    const Graph<Node, Cost> m_graph;
    const std::vector<Node> m_group;

    template <class F>
    constexpr static inline auto dfs(const Graph<Node, Cost>& graph, Node from,
                                     std::vector<bool>& 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<Node, Cost>& graph) {
      int n = graph.size();
      std::vector<Node> order;
      std::vector<bool> is_used(n);
      for (auto from : std::views::iota(0, n)) {
        if (is_used[from]) { continue; }
        dfs(graph, from, is_used, [&](auto f) { order.emplace_back(f); });
      }

      int g = 0;
      std::vector<Node> group(n);
      std::vector<bool> is_used2(n);
      auto rev = graph.reverse();
      for (auto from : order | std::views::reverse) {
        if (is_used2[from]) { continue; }
        dfs(rev, from, is_used2, [&](auto f) { group[f] = g; });
        ++g;
      }
      return group;
    }

  public:
    [[deprecated]] constexpr StronglyConnectedComponents(
        const Graph<Node, Cost>& graph)
        : m_graph(graph), m_group(constructGroup(m_graph)) {}
    // graphのコピーコストが大きいのでこっち推奨

    constexpr StronglyConnectedComponents(Graph<Node, Cost>&& 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(Node a) const { return m_group[a]; }
    constexpr auto isSameGroup(Node a, Node b) const {
      return m_group[a] == m_group[b];
    }
    constexpr auto getGroupNodes() const {
      std::vector<std::vector<Node>> 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<std::pair<Node, Node>, 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<Node, Cost> ret(size());
      for (const auto& [f, t] : st) { ret.addArc(f, t); }
      return ret;
    }
  };
}  // namespace mtd

#line 2 "Library/Graph/Normal/Topological.hpp"

#line 6 "Library/Graph/Normal/Topological.hpp"

#line 8 "Library/Graph/Normal/Topological.hpp"

namespace mtd {
  template <class Node, class Cost>
  auto topological_order(const mtd::Graph<Node, Cost>& graph) {
    std::vector<Node> cnt(graph.size());
    for (auto [_, v] : graph.getEdgesExcludeCost()) { ++cnt[v]; }

    std::deque<Node> q;
    for (auto [nd, c] : cnt | std::views::enumerate) {
      if (c == 0) { q.emplace_back(nd); }
    }

    std::vector<Node> 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;
  }
}  // namespace mtd

#line 7 "Test/Graph/Normal/Topological.test.cpp"
// end:tag includes

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.addArc(u, v - 1);
    }
  }

  auto scc = mtd::StronglyConnectedComponents(std::move(graph));
  auto scc_graph = scc.getGroupGraph();
  auto scc_nodes = scc.getGroupNodes();

  int now = -1;
  bool yes = true;
  for (auto u : mtd::topological_order(scc_graph)) {
    bool ex = (now == -1 ? u == scc.group(0) : false);
    if (now > -1) {
      for (auto [v, _] : scc_graph.getEdges(now)) { ex |= (u == v); }
    }
    yes &= ex;
    now = u;
  }

  std::cout << (yes ? "Yes" : "No") << std::endl;
}

Back to top page