Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.5 kB
4
Indexable
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <set>

struct Pair {
  int16_t first;
  int16_t second;
  Pair() {
    first = 0;
    second = 0;
  }
  Pair(int16_t a, int16_t b) {
    first = a;
    second = b;
  }
};

struct Graph {
  std::vector<std::vector<std::pair<int, int>>> graph;
};

enum class Colours { WHITE, GREY, BLACK };

void DfsVisit(const Graph& gr, const int16_t& vert, std::vector<Colours>& colors, std::vector<int16_t>& time_up,
              std::vector<int16_t>& time_in, int16_t& time, std::vector<int>& res, int16_t par = -1) {
  time_in[vert] = time++;
  time_up[vert] = time_in[vert];
  colors[vert] = Colours::GREY;
  for (size_t i = 0; i < gr.graph[vert].size(); ++i) {
    int16_t to = gr.graph[vert][i].first;
    if (to == par) {
      continue;
    }
    if (colors[to] == Colours::GREY) {
      time_up[vert] = std::min(time_up[vert], time_in[to]);
    }
    if (colors[to] == Colours::WHITE) {
      DfsVisit(gr, to, colors, time_up, time_in, time, res, vert);
      time_up[vert] = std::min(time_up[vert], time_up[to]);
      if (time_up[to] > time_in[vert]) {
        res.emplace_back(gr.graph[vert][i].second);
      }
    }
  }
}

Graph MakeGraph(const int16_t& num, const int32_t& edg, std::vector<Pair>& edgs) {
  Graph gr;
  gr.graph.resize(num);
  for (int32_t i = 0; i < edg; ++i) {
    int16_t fst, scd;
    std::cin >> fst >> scd;
    gr.graph[fst - 1].emplace_back(scd - 1, i + 1);
    gr.graph[scd - 1].emplace_back(fst - 1, i + 1);
    edgs.emplace_back(fst - 1, scd - 1);
  }
  return gr;
}

std::set<int> Bridges(std::vector<Pair>& edgs) {
  int16_t num;
  int32_t edg;
  std::cin >> num >> edg;
  Graph gr = MakeGraph(num, edg, edgs);
  std::vector<int16_t> time_in(num, -1);
  std::vector<int16_t> time_up(num, -1);
  std::vector<Colours> colors(num, Colours::WHITE);
  int16_t time = 0;
  std::set<int> res;
  for (int16_t i = 0; i < num; ++i) {
    if (colors[i] == Colours::WHITE) {
      std::vector<int> tmp_res;
      DfsVisit(gr, i, colors, time_up, time_in, time, tmp_res);
      for (size_t j = 0; j < tmp_res.size(); ++j) {
        res.emplace(tmp_res[j]);
      }
    }
  }
  return res;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  std::vector<Pair> edgs;
  std::set<int> res = Bridges(edgs);
  std::cout << res.size() << '\n';
  std::set<int32_t> answ;
  for (auto i : res) {
    std::cout << i << ' ';
  }
}