cp-library

C++ Library for Competitive Programming

View the Project on GitHub emthrm/cp-library

:heavy_check_mark: グラフ/unicyclic graph
(test/graph/unicyclic_graph.test.cpp)

Depends on

Code

/*
 * @title グラフ/unicyclic graph
 *
 * verification-helper: PROBLEM https://yukicoder.me/problems/no/1254
 */

#include <algorithm>
#include <iostream>
#include <map>
#include <utility>
#include <vector>

#include "emthrm/graph/edge.hpp"
#include "emthrm/graph/unicyclic_graph.hpp"

int main() {
  int n;
  std::cin >> n;
  std::map<std::pair<int, int>, int> edges;
  emthrm::UnicyclicGraph<bool> namori(n);
  for (int i = 0; i < n; ++i) {
    int a, b;
    std::cin >> a >> b;
    --a; --b;
    edges[std::minmax(a, b)] = i;
    namori.add_edge(a, b, false);
  }
  namori.build();
  std::vector<bool> bridge(n, false);
  for (const emthrm::Edge<bool>& e : namori.loop) {
    bridge[edges[std::minmax(e.src, e.dst)]] = true;
  }
  std::vector<int> p;
  for (int i = 0; i < n; ++i) {
    if (bridge[i]) p.emplace_back(i);
  }
  const int k = p.size();
  std::cout << k << '\n';
  for (int i = 0; i < k; ++i) {
    std::cout << p[i] + 1 << " \n"[i + 1 == k];
  }
  return 0;
}
#line 1 "test/graph/unicyclic_graph.test.cpp"
/*
 * @title グラフ/unicyclic graph
 *
 * verification-helper: PROBLEM https://yukicoder.me/problems/no/1254
 */

#include <algorithm>
#include <iostream>
#include <map>
#include <utility>
#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 1 "include/emthrm/graph/unicyclic_graph.hpp"



#include <cassert>
#include <iterator>
#include <queue>
#line 8 "include/emthrm/graph/unicyclic_graph.hpp"

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 10 "include/emthrm/graph/unicyclic_graph.hpp"

namespace emthrm {

template <typename CostType>
struct UnicyclicGraph {
  std::vector<bool> is_in_loop;
  std::vector<int> belong, mapping;
  std::vector<Edge<CostType>> loop;
  std::vector<std::vector<int>> invs;
  std::vector<std::vector<std::vector<Edge<CostType>>>> forest;

  explicit UnicyclicGraph(const int n)
      : is_in_loop(n, false), belong(n, -1), mapping(n, -1), n(n), graph(n) {}

  void add_edge(const int src, const int dst, const CostType cost = 0) {
    const int id = srcs.size();
    srcs.emplace_back(src);
    dsts.emplace_back(dst);
    costs.emplace_back(cost);
    graph[src].emplace_back(id);
    if (dst != src) [[likely]] graph[dst].emplace_back(id);
  }

  void build() {
    dfs(-1, 0);
    std::queue<int> que;
    for (const Edge<CostType>& e : loop) {
      const int root = e.src, forest_id = forest.size();
      belong[root] = forest_id;
      mapping[root] = 0;
      std::vector<int> inv{root};
      std::vector<std::vector<Edge<CostType>>> tree(1);
      que.emplace(root);
      while (!que.empty()) {
        const int ver = que.front();
        que.pop();
        for (const int id : graph[ver]) {
          const int dst = destination(id, ver);
          if (belong[dst] == -1 && !is_in_loop[dst]) {
            const int idx = tree.size();
            belong[dst] = forest_id;
            mapping[dst] = idx;
            inv.emplace_back(dst);
            tree[mapping[ver]].emplace_back(mapping[ver], idx, costs[id]);
            tree.emplace_back(std::vector<Edge<CostType>>{
                Edge<CostType>(idx, mapping[ver], costs[id])});
            que.emplace(dst);
          }
        }
      }
      if (inv.size() == 1) {
        belong[root] = mapping[root] = -1;
      } else {
        invs.emplace_back(inv);
        forest.emplace_back(tree);
      }
    }
  }

 private:
  const int n;
  std::vector<int> srcs, dsts;
  std::vector<CostType> costs;
  std::vector<std::vector<int>> graph;

  int destination(const int id, const int s) const {
    return (srcs[id] == s ? dsts : srcs)[id];
  }

  bool dfs(const int prev_id, const int ver) {
    is_in_loop[ver] = true;
    for (const int id : graph[ver]) {
      if (id == prev_id) continue;
      const int dst = destination(id, ver);
      loop.emplace_back(ver, dst, costs[id]);
      if (is_in_loop[dst]) {
        for (int i = loop.size() - 1; i >= 0; --i) {
          if (loop[i].src == dst) {
            for (int j = 0; j < i; ++j) {
              is_in_loop[loop[j].src] = false;
            }
            loop.erase(loop.begin(), std::next(loop.begin(), i));
            return true;
          }
        }
        assert(false);
      }
      if (dfs(id, dst)) return true;
      loop.pop_back();
    }
    is_in_loop[ver] = false;
    return false;
  }
};

}  // namespace emthrm


#line 15 "test/graph/unicyclic_graph.test.cpp"

int main() {
  int n;
  std::cin >> n;
  std::map<std::pair<int, int>, int> edges;
  emthrm::UnicyclicGraph<bool> namori(n);
  for (int i = 0; i < n; ++i) {
    int a, b;
    std::cin >> a >> b;
    --a; --b;
    edges[std::minmax(a, b)] = i;
    namori.add_edge(a, b, false);
  }
  namori.build();
  std::vector<bool> bridge(n, false);
  for (const emthrm::Edge<bool>& e : namori.loop) {
    bridge[edges[std::minmax(e.src, e.dst)]] = true;
  }
  std::vector<int> p;
  for (int i = 0; i < n; ++i) {
    if (bridge[i]) p.emplace_back(i);
  }
  const int k = p.size();
  std::cout << k << '\n';
  for (int i = 0; i < k; ++i) {
    std::cout << p[i] + 1 << " \n"[i + 1 == k];
  }
  return 0;
}
Back to top page