Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- std::vector<std::vector<std::pair<int, int>>> a;
- std::vector<int> tin, bridges;
- int timer = 0;
- int dfs(int i, int prev) {
- if (tin[i] != 0)
- return tin[i];
- ++timer;
- tin[i] = timer;
- int tmp_time = tin[i];
- for (auto x : a[i])
- if (x.first != prev) {
- int t = dfs(x.first, i);
- if (t > tin[i])
- bridges.push_back(x.second);
- tmp_time = std::min(t, tmp_time);
- }
- tin[i] = tmp_time;
- return tmp_time;
- }
- int main() {
- int n, m;
- std::cin >> n >> m;
- a.resize(n);
- tin.resize(n, 0);
- for (int i = 1; i != m + 1; ++i) {
- int x, y;
- std::cin >> x >> y;
- --x;
- --y;
- a[x].push_back(std::make_pair(y, i));
- a[y].push_back(std::make_pair(x, i));
- }
- for (int i = 0; i != n; ++i)
- if (tin[i] == 0)
- dfs(i, -1);
- sort(bridges.begin(), bridges.end());
- std::cout << bridges.size() << std::endl;
- for (auto x : bridges)
- std::cout << x << " ";
- system("pause");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement