#565476 (C++17(gcc12)) No.1254 補強への架け橋

• 問題: No.1254 補強への架け橋
• ユーザー: jell
• 提出日時: 2020-10-10 02:08:35
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 6,722 bytes
• コンパイル時間: 1,822 ms
• コンパイル使用メモリ: 89,060 KB
• 最終ジャッジ日時: 2025-01-15 06:10:39
• ジャッジサーバーID （参考情報）: judge5 / judge5

コンパイルメッセージ

Library/graph/undirected/two_edge_connected_components.hpp:7:20: error: 'size_t' does not name a type
Library/graph/undirected/two_edge_connected_components.hpp:4:1: note: 'size_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
Library/graph/undirected/two_edge_connected_components.hpp:8:15: error: 'size_t' was not declared in this scope; did you mean 'std::size_t'?
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/cassert:43,
                 from Library/graph/undirected/two_edge_connected_components.hpp:2:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/x86_64-pc-linux-gnu/bits/c++config.h:298:33: note: 'std::size_t' declared here
  298 |   typedef __SIZE_TYPE__         size_t;
      |                                 ^~~~~~
Library/graph/undirected/two_edge_connected_components.hpp:8:21: error: template argument 1 is invalid
Library/graph/undirected/two_edge_connected_components.hpp:8:21: error: template argument 2 is invalid
Library/graph/undirected/two_edge_connected_components.hpp:8:8: error: '<expression error>' in namespace 'std' does not name a type
Library/graph/undirected/two_edge_connected_components.hpp:9:27: error: 'size_t' was not declared in this scope; did you mean 'std::size_t'?
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/x86_64-pc-linux-gnu/bits/c++config.h:298:33: note: 'std::size_t' declared here
  298 |   typedef __SIZE_TYPE__         size_t;
      |                                 ^~~~~~
Library/graph/undirected/two_edge_connected_components.hpp:9:27: error: template argument 1 is invalid
Library/graph/undirected/two_edge_connected_components.hpp:9:27: error: template argument 2 is invalid
Library/graph/undirected/two_edge_connected_components.hpp:9:33: error: template argument 1 is invalid
Library/graph/undirected/two_edge_connected_components.hpp:9:33: error: template argument 2 is invalid
Library/graph/undirected/two_edge_connected_components.hpp

ソースコード

#line 1 "Library/test/yukicoder/1254.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1254"
#line 2 "Library/graph/undirected/two_edge_connected_components.hpp"
#include <cassert>
#include <vector>

// instance: an undirected and not necessarily simple graph
class two_edge_connected_component {
  static constexpr size_t nil = -1;
  std::vector<size_t> stack, low, comp;
  std::vector<std::vector<size_t>> graph, tree, memb;

  void make(size_t now, size_t pre) {
    size_t ord = low[now] = stack.size();
    stack.emplace_back(now);
    std::vector<size_t> brid;
    for (size_t to : graph[now]) {
      if (to == pre) {
        pre = nil;
        continue;
      }
      if (low[to] == nil) make(to, now);
      if (low[to] > ord) {
        brid.emplace_back(to);
        graph[to].emplace_back(now);
      } else if (low[now] > low[to])
        low[now] = low[to];
    }
    brid.swap(graph[now]);
    if (ord == low[now]) {
      auto pos = stack.end();
      tree.resize(tree.size() + 1);
      auto &adjc = tree.back();
      do {
        --pos;
        comp[*pos] = memb.size();
        for (size_t u : graph[*pos]) adjc.emplace_back(comp[u]);
      } while (*pos != now);
      memb.emplace_back(pos, stack.end());
      stack.erase(pos, stack.end());
    }
  }

 public:
  two_edge_connected_component(size_t n) : comp(n), graph(n) {
    stack.reserve(n), tree.reserve(n), memb.reserve(n);
  }

  void add_edge(size_t u, size_t v) {
    assert(u < size()), assert(v < size());
    graph[u].emplace_back(v), graph[v].emplace_back(u);
  }

  void make() {
    low.assign(size(), nil);
    for (size_t v = 0; v != size(); ++v)
      if (low[v] == nil) make(v, nil);
  }

  size_t size() const { return graph.size(); }

  size_t size(size_t i) {
    assert(i < count());
    return memb[i].size();
  }

  size_t count() const { return memb.size(); }

  size_t operator[](size_t v) const {
    assert(v < size());
    return comp[v];
  }

  const std::vector<size_t> &bridge(size_t v) const {
    assert(v < size());
    return graph[v];
  }

  const std::vector<size_t> &component(size_t i) const {
    assert(i < count());
    return memb[i];
  }

  const std::vector<std::vector<size_t>> &bridge_tree() const { return tree; }
};  // class two_edge_connected_component
#line 2 "Library/utils/stream.hpp"
#include <iostream>
#include <tuple>

#line 2 "Library/utils/sfinae.hpp"
#include <cstdint>
#include <iterator>
#include <type_traits>

template <class type, template <class> class trait>
using enable_if_trait_type = typename std::enable_if<trait<type>::value>::type;

template <class Container>
using element_type = typename std::decay<decltype(
    *std::begin(std::declval<Container&>()))>::type;

template <class T, class = int> struct mapped_of {
  using type = element_type<T>;
};
template <class T>
struct mapped_of<T,
                 typename std::pair<int, typename T::mapped_type>::first_type> {
  using type = typename T::mapped_type;
};
template <class T> using mapped_type = typename mapped_of<T>::type;

template <class T, class = void> struct is_integral_ext : std::false_type {};
template <class T>
struct is_integral_ext<
    T, typename std::enable_if<std::is_integral<T>::value>::type>
    : std::true_type {};
template <> struct is_integral_ext<__int128_t> : std::true_type {};
template <> struct is_integral_ext<__uint128_t> : std::true_type {};
#if __cplusplus >= 201402
template <class T>
constexpr static bool is_integral_ext_v = is_integral_ext<T>::value;
#endif

template <typename T, typename = void> struct multiplicable_uint {
  using type = uint_least32_t;
};
template <typename T>
struct multiplicable_uint<T, typename std::enable_if<(2 < sizeof(T))>::type> {
  using type = uint_least64_t;
};
template <typename T>
struct multiplicable_uint<T, typename std::enable_if<(4 < sizeof(T))>::type> {
  using type = __uint128_t;
};
#line 6 "Library/utils/stream.hpp"
namespace std {
template <class T, class U> istream &operator>>(istream &is, pair<T, U> &p) {
  return is >> p.first >> p.second;
}
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  return os << p.first << ' ' << p.second;
}
template <class tuple_t, size_t index> struct tuple_is {
  static istream &apply(istream &is, tuple_t &t) {
    tuple_is<tuple_t, index - 1>::apply(is, t);
    return is >> get<index>(t);
  }
};
template <class tuple_t> struct tuple_is<tuple_t, SIZE_MAX> {
  static istream &apply(istream &is, tuple_t &t) { return is; }
};
template <class... T> istream &operator>>(istream &is, tuple<T...> &t) {
  return tuple_is<tuple<T...>, tuple_size<tuple<T...>>::value - 1>::apply(is,
                                                                          t);
}
template <class tuple_t, size_t index> struct tuple_os {
  static ostream &apply(ostream &os, const tuple_t &t) {
    tuple_os<tuple_t, index - 1>::apply(os, t);
    return os << ' ' << get<index>(t);
  }
};
template <class tuple_t> struct tuple_os<tuple_t, 0> {
  static ostream &apply(ostream &os, const tuple_t &t) {
    return os << get<0>(t);
  }
};
template <class tuple_t> struct tuple_os<tuple_t, SIZE_MAX> {
  static ostream &apply(ostream &os, const tuple_t &t) { return os; }
};
template <class... T> ostream &operator<<(ostream &os, const tuple<T...> &t) {
  return tuple_os<tuple<T...>, tuple_size<tuple<T...>>::value - 1>::apply(os,
                                                                          t);
}
template <class Container, typename Value = element_type<Container>>
typename enable_if<!is_same<typename decay<Container>::type, string>::value &&
                       !is_same<typename decay<Container>::type, char *>::value,
                   istream &>::type
operator>>(istream &is, Container &cont) {
  for (auto &&e : cont) is >> e;
  return is;
}
template <class Container, typename Value = element_type<Container>>
typename enable_if<!is_same<typename decay<Container>::type, string>::value &&
                       !is_same<typename decay<Container>::type, char *>::value,
                   ostream &>::type
operator<<(ostream &os, const Container &cont) {
  bool head = true;
  for (auto &&e : cont) head ? head = 0 : (os << ' ', 0), os << e;
  return os;
}
}  // namespace std
#line 4 "Library/test/yukicoder/1254.test.cpp"

int main() {
  int n;
  std::cin >> n;
  two_edge_connected_component becc(n);
  std::vector<std::pair<int, int>> edges(n);
  for (auto &&[a, b] : edges) {
    std::cin >> a >> b;
    --a, --b;
    becc.add_edge(a, b);
  }
  becc.make();
  std::vector<int> ans;
  int id = 0;
  for (auto &&[a, b] : edges) {
    ++id;
    if (becc[a] == becc[b]) ans.emplace_back(id);
  }
  std::cout << ans.size() << "\n" << ans << "\n";
}