Untitled
unknown
plain_text
a year ago
2.5 kB
4
Indexable
Never
#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 << ' '; } }