結果

問題 No.1254 補強への架け橋
ユーザー emthrm
提出日時 2021-04-19 04:57:52
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 213 ms / 2,000 ms
コード長 4,594 bytes
コンパイル時間 2,841 ms
コンパイル使用メモリ 226,804 KB
最終ジャッジ日時 2025-01-20 22:01:49
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 123
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 1000000007;
// constexpr int MOD = 998244353;
constexpr int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << fixed << setprecision(20);
  }
} iosetup;

template <typename CostType>
struct Edge {
  int src, dst; CostType cost;
  Edge(int src, int dst, CostType cost = 0) : src(src), dst(dst), cost(cost) {}
  inline bool operator<(const Edge &x) const {
    return cost != x.cost ? cost < x.cost : dst != x.dst ? dst < x.dst : src < x.src;
  }
  inline bool operator<=(const Edge &x) const { return !(x < *this); }
  inline bool operator>(const Edge &x) const { return x < *this; }
  inline bool operator>=(const Edge &x) const { return !(*this < x); }
};

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

  UnicyclicGraph(int n) : n(n), is_in_loop(n, false), belong(n, -1), mp(n, -1), graph(n) {}

  void add_edge(int src_i, int dst_i, CostType cost_i) {
    int id = src.size();
    graph[src_i].emplace_back(id);
    graph[dst_i].emplace_back(id);
    src.emplace_back(src_i);
    dst.emplace_back(dst_i);
    cost.emplace_back(cost_i);
  }

  void build() {
    dfs(-1, 0);
    for (int i = 0; i < n; ++i) {
      if (is_in_loop[i] && graph[i].size() > 2) {
        int idx = forest.size();
        forest.emplace_back(std::vector<std::vector<Edge<CostType>>>(1));
        belong[i] = idx;
        mp[i] = 0;
        inv.emplace_back(std::vector<int>{i});
        std::queue<int> que({i});
        while (!que.empty()) {
          int ver = que.front();
          que.pop();
          for (int id : graph[ver]) {
            int to = destination(id, ver);
            if (belong[to] == -1 && !is_in_loop[to]) {
              int nx = forest[idx].size();
              forest[idx].emplace_back();
              forest[idx][mp[ver]].emplace_back(mp[ver], nx, cost[id]);
              forest[idx][nx].emplace_back(nx, mp[ver], cost[id]);
              belong[to] = idx;
              mp[to] = nx;
              inv[idx].emplace_back(to);
              que.emplace(to);
            }
          }
        }
      }
    }
  }

private:
  int n;
  std::vector<std::vector<int>> graph;
  std::vector<int> src, dst;
  std::vector<CostType> cost;

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

  bool dfs(int prev_id, int ver) {
    is_in_loop[ver] = true;
    for (int id : graph[ver]) {
      if (id != prev_id) {
        int to = destination(id, ver);
        loop.emplace_back(ver, to, cost[id]);
        if (is_in_loop[to]) {
          for (int i = static_cast<int>(loop.size()) - 2; i >= 0; --i) {
            if (loop[i].src == to) {
              for (int j = 0; j < i; ++j) is_in_loop[loop[j].src] = false;
              loop.erase(loop.begin(), loop.begin() + i);
              break;
            }
          }
          return true;
        }
        if (dfs(id, to)) return true;
        loop.pop_back();
      }
    }
    is_in_loop[ver] = false;
    return false;
  }
};

int main() {
  int n;
  std::cin >> n;
  std::map<std::pair<int, int>, int> edge;
  UnicyclicGraph<bool> namori(n);
  for (int i = 0; i < n; ++i) {
    int a, b;
    std::cin >> a >> b;
    --a; --b;
    if (a > b) std::swap(a, b);
    edge[{a, b}] = i;
    namori.add_edge(a, b, false);
  }
  namori.build();
  std::vector<bool> bridge(n, false);
  for (const Edge<bool> &e : namori.loop) {
    int a = e.src, b = e.dst;
    if (a > b) std::swap(a, b);
    bridge[edge[{a, b}]] = true;
  }
  std::vector<int> p;
  for (int i = 0; i < n; ++i) {
    if (bridge[i]) p.emplace_back(i);
  }
  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;
}
0