cp-includes

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub rsalesc/cp-includes

:heavy_check_mark: tests/yosupo/chordal.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/chordal_graph_recognition"

#include <bits/stdc++.h>
#include "Graph.cpp"
#include "graphs/Chordal.cpp"
#define int long long
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ms(v, x) memset((v), (x), sizeof(v))
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
#define iopt ios::sync_with_stdio(false); cin.tie(0)
#define untie(p, a, b) decltype(p.first) a = p.first, decltype(p.second) b = p.second
 
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int power(int x, int p, int MOD) {
    if(p == 0) return 1%MOD;
    if(p == 1) return x%MOD;
    int res = power(x, p/2, MOD);
    res = (long long)res*res%MOD;
    if(p&1) res = (long long)res*x%MOD;
    return res;
}
 
typedef pair<int, int> ii;
typedef long double LD;
typedef vector<int> vi;

using namespace lib;

int32_t main(){
    // Scanner sc(stdin);
    // Printer pr(stdout);
    iopt;

    int n, m;
    cin >> n >> m;
    graph::Graph<> g(n);

    for(int i = 0; i < m; i++) {
      int a, b;
      cin >> a >> b;
      g.add_2edge(a, b);
    }

    auto ch = graph::make_chordal(g);
    if(ch.is_valid()) {
      cout << "YES" << endl;
      for(int x : ch.order) cout << x << " ";
      cout << endl;
    } else {
      cout << "NO" << endl;
      cout << ch.induced_cycle().size() << endl;
      for(int x : ch.induced_cycle()) cout << x << " ";
      cout << endl;
    }
    return 0;
}
#line 1 "tests/yosupo/chordal.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/chordal_graph_recognition"

#include <bits/stdc++.h>
#line 1 "Graph.cpp"


#line 1 "Traits.cpp"


#line 4 "Traits.cpp"

namespace lib {
using namespace std;
namespace traits {

template <typename...> struct make_void { using type = void; };

template <typename... T> using void_t = typename make_void<T...>::type;

/// keep caide
template <typename Iterator>
using IteratorCategory = typename iterator_traits<Iterator>::iterator_category;

/// keep caide
template <typename Container>
using IteratorCategoryOf = IteratorCategory<typename Container::iterator>;

/// keep caide
template <typename Iterator>
using IteratorValue = typename iterator_traits<Iterator>::value_type;

/// keep caide
template <typename Container>
using IteratorValueOf = IteratorValue<typename Container::iterator>;

/// keep caide
template <typename Iterator>
using IsRandomIterator =
    is_base_of<random_access_iterator_tag, IteratorCategory<Iterator>>;

/// keep caide
template <typename Iterator>
using IsInputIterator =
    is_base_of<input_iterator_tag, IteratorCategory<Iterator>>;

/// keep caide
template <typename Iterator>
using IsBidirectionalIterator =
    is_base_of<bidirectional_iterator_tag, IteratorCategory<Iterator>>;

/// keep caide
template <typename Container>
using HasRandomIterator =
    is_base_of<random_access_iterator_tag, IteratorCategoryOf<Container>>;

/// keep caide
template <typename Container>
using HasInputIterator =
    is_base_of<input_iterator_tag, IteratorCategoryOf<Container>>;

/// keep caide
template <typename Container>
using HasBidirectionalIterator =
    is_base_of<bidirectional_iterator_tag, IteratorCategoryOf<Container>>;
} // namespace traits
} // namespace lib


#line 1 "utils/Wrappers.cpp"


#line 4 "utils/Wrappers.cpp"

namespace lib {
using namespace std;
namespace graph {
template <typename T> struct Edge {
  const int from, to;
  T data;
};

template <> struct Edge<void> { const int from, to; };

template <typename T> struct VertexWrapper { T data; };

template <> struct VertexWrapper<void> {};
} // namespace graph
} // namespace lib


#line 6 "Graph.cpp"

namespace lib {
using namespace std;
namespace graph {
template <typename V = void, typename E = void, bool Directed = false>
struct GraphImpl {
  typedef GraphImpl<V, E> self_type;
  typedef vector<vector<int>> adj_list;
  typedef Edge<E> edge_type;
  typedef VertexWrapper<V> vertex_type;

  const static bool directed = Directed;

  vector<edge_type> edges;
  adj_list adj;

  vector<vertex_type> vertices;

  class iterator {
  public:
    typedef iterator self_type;
    typedef edge_type value_type;
    typedef edge_type &reference;
    typedef edge_type *pointer;
    typedef std::forward_iterator_tag iterator_category;
    typedef int difference_type;
    iterator(vector<int> *adj, vector<edge_type> *edges, int ptr = 0)
        : adj_(adj), edges_(edges), ptr_(ptr) {}
    self_type operator++() {
      ptr_++;
      return *this;
    }
    self_type operator++(int junk) {
      self_type i = *this;
      ptr_++;
      return i;
    }
    reference operator*() { return (*edges_)[(*adj_)[ptr_]]; }
    pointer operator->() { return &(*edges_)[(*adj_)[ptr_]]; }
    bool operator==(const self_type &rhs) const {
      return adj_ == rhs.adj_ && ptr_ == rhs.ptr_;
    }
    bool operator!=(const self_type &rhs) const { return !(*this == rhs); }

  private:
    vector<int> *adj_;
    vector<edge_type> *edges_;
    int ptr_;
  };

  class const_iterator {
  public:
    typedef const_iterator self_type;
    typedef edge_type value_type;
    typedef edge_type &reference;
    typedef edge_type *pointer;
    typedef std::forward_iterator_tag iterator_category;
    typedef int difference_type;
    const_iterator(vector<int> *adj, vector<edge_type> *edges, int ptr = 0)
        : adj_(adj), edges_(edges), ptr_(ptr) {}
    self_type operator++() {
      ptr_++;
      return *this;
    }
    self_type operator++(int junk) {
      self_type i = *this;
      ptr_++;
      return i;
    }
    const value_type &operator*() { return (*edges_)[(*adj_)[ptr_]]; }
    const value_type *operator->() { return &(*edges_)[(*adj_)[ptr_]]; }
    bool operator==(const self_type &rhs) const {
      return adj_ == rhs.adj_ && ptr_ == rhs.ptr_;
    }
    bool operator!=(const self_type &rhs) const { return !(*this == rhs); }

  private:
    vector<int> *adj_;
    vector<edge_type> *edges_;
    int ptr_;
  };

  struct iterable {
    vector<int> *adj_;
    vector<edge_type> *edges_;

    iterable(vector<int> *adj, vector<edge_type> *edges)
        : adj_(adj), edges_(edges) {}

    inline iterator begin() { return iterator(adj_, edges_); }
    inline iterator end() { return iterator(adj_, edges_, adj_->size()); }

    inline const_iterator cbegin() const {
      return const_iterator(adj_, edges_);
    }
    inline const_iterator cend() const {
      return const_iterator(adj_, edges_, adj_->size());
    }

    inline const_iterator begin() const { return cbegin(); }
    inline const_iterator end() const { return cend(); }

    inline edge_type &operator[](int i) { return (*edges_)[(*adj_)[i]]; }
    inline const edge_type &operator[](int i) const {
      return (*edges_)[(*adj_)[i]];
    }

    inline int index(int i) const { return (*adj_)[i]; }
    inline int size() const { return adj_->size(); }
  };

  GraphImpl() {}

  template <typename S = V,
            typename enable_if<is_void<S>::value>::type * = nullptr>
  GraphImpl(size_t n) : adj(n) {}

  template <typename S = V,
            typename enable_if<!is_void<S>::value>::type * = nullptr>
  GraphImpl(size_t n) : adj(n), vertices(n) {}

  inline iterable n_edges(int i) { return iterable(&adj[i], &edges); }
  inline const iterable n_edges(int i) const {
    return iterable(const_cast<vector<int> *>(&adj[i]),
                    const_cast<vector<edge_type> *>(&edges));
  }
  inline int degree(int i) const { return adj[i].size(); }

  inline int size() const { return adj.size(); }
  inline int edge_size() const { return edges.size(); }
  inline edge_type &edge(int i) { return edges[i]; }
  inline edge_type edge(int i) const { return edges[i]; }

  inline vector<edge_type> all_edges() const { return edges; }

  template <typename S = V,
            typename enable_if<!is_void<S>::value>::type * = nullptr>
  inline S &vertex(int i) {
    return vertices[i];
  }

  template <typename S = V,
            typename enable_if<!is_void<S>::value>::type * = nullptr>
  inline V vertex(int i) const {
    return vertices[i];
  }

  template <typename S = V,
            typename enable_if<is_void<S>::value>::type * = nullptr>
  inline void add_vertex() {
    adj.emplace_back();
  }

  template <typename S = V,
            typename enable_if<!is_void<S>::value>::type * = nullptr>
  inline S &add_vertex() {
    adj.emplace_back();
    return vertices.emplace_back().data;
  }

  template <typename S = E,
            typename enable_if<is_void<S>::value>::type * = nullptr>
  inline void add_edge_(int u, int v) {
    adj[u].push_back(edges.size());
    edges.push_back({u, v});
  }

  template <typename S = E,
            typename enable_if<!is_void<S>::value>::type * = nullptr>
  inline S &add_edge_(int u, int v) {
    adj[u].push_back(edges.size());
    edges.push_back({u, v});
    return edges.back().data;
  }

  void add_2edge(int u, int v) {
    add_edge_(u, v);
    add_edge_(v, u);
  }

  template <typename S = E,
            typename enable_if<!is_void<S>::value>::type * = nullptr>
  inline void add_2edge(int u, int v, const S &data) {
    add_edge_(u, v) = data;
    add_edge_(v, u) = data;
  }

  template <typename S = E,
            typename enable_if<is_void<S>::value && Directed>::type * = nullptr>
  inline void add_edge(int u, int v) {
    adj[u].push_back(edges.size());
    edges.push_back({u, v});
  }

  template <typename S = E,
            typename enable_if<!is_void<S>::value && Directed>::type * = nullptr>
  inline S &add_edge(int u, int v) {
    adj[u].push_back(edges.size());
    edges.push_back({u, v});
    return edges.back().data;
  }
};

template<typename V = void, typename E = void>
using Graph = GraphImpl<V, E, false>;

template<typename V = void, typename E = void>
using DirectedGraph = GraphImpl<V, E, true>;

template <typename V = void, typename E = void>
struct RootedForest : public DirectedGraph<V, E> {
  typedef RootedForest<V, E> self_type;
  using typename DirectedGraph<V, E>::adj_list;
  using typename DirectedGraph<V, E>::edge_type;
  using DirectedGraph<V, E>::DirectedGraph;
  using DirectedGraph<V, E>::adj;
  using DirectedGraph<V, E>::edge;
  vector<int> p, pe;

  void build_parents() {
    if ((int)p.size() == this->size())
      return;

    int n = this->size();
    stack<int> st;
    vector<bool> vis(n);
    p.assign(n, -1), pe.assign(n, -1);
    for (int i = 0; i < n; i++) {
      if (!vis[i]) {
        st.push(i);
        vis[i] = true;
        while (!st.empty()) {
          int u = st.top();
          st.pop();

          for (int k : adj[u]) {
            int v = edge(k).to;
            vis[v] = true;
            st.push(v), pe[v] = k, p[v] = u;
          }
        }
      }
    }
  }

  inline int parent(int i) const {
    const_cast<self_type *>(this)->build_parents();
    return p[i];
  }

  inline bool is_root(int i) const { return parent(i) != -1; }

  inline edge_type &parent_edge(int i) {
    build_parents();
    return edge(pe[i]);
  }
  inline edge_type &parent_edge(int i) const {
    const_cast<self_type *>(this)->build_parents();
    return edge(pe[i]);
  }

  vector<int> roots() const {
    vector<int> res;
    const_cast<self_type *>(this)->build_parents();
    int n = this->size();

    for (int i = 0; i < n; i++)
      if (p[i] == -1)
        res.push_back(i);
    return res;
  }
};

template <typename V = void, typename E = void>
struct RootedTree : public RootedForest<V, E> {
  using typename RootedForest<V, E>::adj_list;
  int root;

  RootedTree(int n, int root) : RootedForest<V, E>(n) {
    assert(n > 0);
    assert(root < n);
    this->root = root;
  }

  RootedTree(const adj_list &adj, int root) : RootedForest<V, E>(adj) {
    assert(adj.size() > 0);
    assert(root < adj.size());
    this->root = root;
  }
};

namespace builders {
namespace {
template <typename F, typename G>
void dfs_rooted_forest(F &forest, const G &graph, int u, vector<bool> &vis) {
  vis[u] = true;
  for (const auto &ed : graph.n_edges(u)) {
    int v = ed.to;
    if (!vis[v]) {
      forest.add_edge(u, v);
      dfs_rooted_forest(forest, graph, v, vis);
    }
  }
}
} // namespace

template <typename A, typename B>
RootedForest<A, B> make_rooted_forest(const Graph<A, B> &graph,
                                      const vector<int> &roots) {
  RootedForest<A, B> res(graph.size());
  vector<bool> vis(graph.size());
  for (int i : roots)
    if (!vis[i])
      dfs_rooted_forest(res, graph, i, vis);
  for (int i = 0; i < graph.size(); i++)
    if (!vis[i])
      dfs_rooted_forest(res, graph, i, vis);
  return res;
}
} // namespace builders
} // namespace graph
} // namespace lib


#line 1 "graphs/Chordal.cpp"


#line 1 "utils/FastList.cpp"


#line 4 "utils/FastList.cpp"

namespace lib {
  using namespace std;
namespace list {
template<typename T>
struct Node {
  T val;
  Node *next = nullptr, *prev = nullptr;
  Node() {}
  Node(T v) : val(v) {}

  void clear_links() {
    if(next != nullptr) next->prev = prev;
    if(prev != nullptr) prev->next = next;
    next = prev = nullptr;
  }
};

template<typename T>
void remove(Node<T>* no) {
  if(no != nullptr) no->clear_links();
}

template<typename T>
void append(Node<T>* no, Node<T>* nw) {
  assert(no != nullptr);
  remove(nw);
  if(no->next != nullptr) no->next->prev = nw;
  if(nw != nullptr) {
    nw->next = no->next;
    nw->prev = no;
  }
  no->next = nw;
}

template<typename T>
void prepend(Node<T>* no, Node<T>* nw) {
  assert(no != nullptr);
  remove(nw);
  if(no->prev != nullptr) no->prev->next = nw;
  if(nw != nullptr) {
    nw->prev = no->prev;
    nw->next = no;
  }
  no->prev = nw;
}
} // namespace list
} // namespace lib


#line 5 "graphs/Chordal.cpp"

namespace lib {
  using namespace std;
namespace graph {
namespace {
  using Elements = pair<vector<int>, int>;
  using SetList = lib::list::Node<Elements>;
  shared_ptr<SetList> make_set_list(int n = 0) {
    return make_shared<SetList>(Elements(vector<int>(n), 0));
  }
}
// No parallel edges or self-loops.
template<typename Graph>
vector<int> lex_bfs(const Graph& g) {
  int n = g.size();
  vector<int> res(n);
  vector<int> vis(n);
  vector<pair<shared_ptr<SetList>, int>> inv(n);
  auto data = make_set_list(n);
  for(int i = 0; i < n; i++) {
    data->val.first[i] = i;
    inv[i] = make_pair(data, i);
  }

  auto head = make_set_list();
  list::append(head.get(), data.get());

  for(int i = 0; i < n; i++) {
    auto no = head->next;
    assert(no != nullptr);
    assert(!no->val.first.empty());
    const int u = res[i] = no->val.first.back();
    no->val.first.pop_back();
    if(no->val.first.empty()) list::remove(no);
    vis[u] = 1;

    // Partition
    for(const auto& e : g.n_edges(u)) {
      int v = e.to;
      if(vis[v]) continue;
      auto st = inv[v].first;
      int sz = st->val.first.size();
      if(sz == 1) continue;
      auto idx = inv[v].second;
      swap(st->val.first[idx], st->val.first[sz - 1 - st->val.second]);
      swap(inv[v].second, inv[st->val.first[idx]].second);
      st->val.second++;
    }

    for(const auto& e : g.n_edges(u)) {
      int v = e.to;
      if(vis[v]) continue;
      auto st = inv[v].first;
      int st_sz = st->val.first.size();
      int size_new = st->val.second;
      assert(size_new <= st_sz);
      if(size_new == 0 || size_new == st_sz) {
        st->val.second = 0;
        continue;
      }
      auto new_data = make_set_list(size_new);
      for(int i = 0; i < size_new; i++) {
        new_data->val.first[i] = st->val.first[st_sz - size_new + i];
        inv[new_data->val.first[i]] = {new_data, i};
      }

      st->val.first.resize(st_sz - size_new);
      st->val.second = 0;

      // both st and new_data should have size > 0 at this point
      list::prepend(st.get(), new_data.get());
    }
  }

  return res;
}

template<typename Graph>
struct Chordal {
  mutable vector<int> vis, par;
  mutable vector<int> cyc;

  Graph g;
  vector<int> order, inv;
  mutable bool was_tested = false;
  Chordal(Graph g) : g(g) {
    order = lex_bfs(g);
    reverse(order.begin(), order.end());
    int n = g.size();
    inv = vector<int>(n);
    for(int i = 0; i < n; i++) inv[order[i]] = i;
  }

  bool is_valid() const {
    if(was_tested) return cyc.empty();
    int n = g.size();

    vector<vector<int>> adj(n);
    for(int i = 0; i < n; i++) {
      for(const auto& e : g.n_edges(i)) {
        adj[i].push_back(e.to);
      }
      sort(adj[i].begin(), adj[i].end());
    }

    for(int k = n-2; k >= 0; k--) {
      int i = order[k];
      pair<int, int> best = {1e9, -1};
      for(const auto& e : g.n_edges(i)) {
        if(inv[e.to] > k)
          best = min(best, {inv[e.to], e.to});
      }
      auto v = best.second;
      if(v == -1) continue;
      for(const auto& e : g.n_edges(i)) {
        if(inv[e.to] > inv[v])
          if(!binary_search(adj[v].begin(), adj[v].end(), e.to)) {
            was_tested = true;
            par.assign(n, -1), vis.assign(n, 0);
            queue<int> q;
            vis[e.to] = 1;
            q.push(e.to);
            while(!q.empty()) {
              int x = q.front(); q.pop();
              for(const auto& e2 : g.n_edges(x)) {
                int y = e2.to;
                if(vis[y]) continue;
                if(y == i) continue;
                if(y != v && binary_search(adj[i].begin(), adj[i].end(), y)) continue;
                vis[y] = 1;
                q.push(y);
                par[y] = x;
              }
            }
            cyc.clear();
            cyc.push_back(e.to);
            cyc.push_back(i);
            assert(vis[v]);
            for(auto x = v; x != e.to; x = par[x]) cyc.push_back(x);
            return false;
          }
      }
    }
    was_tested = true;
    return true;
  }

  vector<int> induced_cycle() const { return cyc; }

  vector<int> max_independent_set() const {
    int n = g.size();
    vis.assign(n, 0);

    vector<int> res;
    for(int i : order) {
      if(vis[i]) continue;
      res.push_back(i);
      for(const auto& e : g.n_edges(i)) {
        vis[e.to] = 1;
      }
    }
    return res;
  }
};

template<typename Graph>
Chordal<Graph> make_chordal(const Graph& g) {
  return Chordal<Graph>(g);
}
} // namespace graph
} // namespace lib


#line 6 "tests/yosupo/chordal.test.cpp"
#define int long long
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ms(v, x) memset((v), (x), sizeof(v))
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
#define iopt ios::sync_with_stdio(false); cin.tie(0)
#define untie(p, a, b) decltype(p.first) a = p.first, decltype(p.second) b = p.second
 
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int power(int x, int p, int MOD) {
    if(p == 0) return 1%MOD;
    if(p == 1) return x%MOD;
    int res = power(x, p/2, MOD);
    res = (long long)res*res%MOD;
    if(p&1) res = (long long)res*x%MOD;
    return res;
}
 
typedef pair<int, int> ii;
typedef long double LD;
typedef vector<int> vi;

using namespace lib;

int32_t main(){
    // Scanner sc(stdin);
    // Printer pr(stdout);
    iopt;

    int n, m;
    cin >> n >> m;
    graph::Graph<> g(n);

    for(int i = 0; i < m; i++) {
      int a, b;
      cin >> a >> b;
      g.add_2edge(a, b);
    }

    auto ch = graph::make_chordal(g);
    if(ch.is_valid()) {
      cout << "YES" << endl;
      for(int x : ch.order) cout << x << " ";
      cout << endl;
    } else {
      cout << "NO" << endl;
      cout << ch.induced_cycle().size() << endl;
      for(int x : ch.induced_cycle()) cout << x << " ";
      cout << endl;
    }
    return 0;
}
Back to top page