Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- using namespace std;
- struct edge
- {
- int to;
- int number;
- edge(int to_, int number_) : to(to_), number(number_)
- {}
- };
- bool min(int a, int b)
- {
- return a < b ? a : b;
- }
- vector<vector<edge> > edges;
- vector<bool> bridges;
- vector<int> colour;
- vector<int> enter;
- vector<int> ret;
- int k;
- int time_;
- void dfs(int v, int prev_v)
- {
- cout << v << endl;
- colour[v] = 1;
- enter[v] = ++time_;
- ret[v] = enter[v];
- int u;
- int number;
- for (size_t i = 0; i < edges[v].size(); i++)
- {
- u = edges[v][i].to;
- if (u == prev_v)
- continue;
- if (colour[u] == 1)
- ret[v] = min(ret[v], enter[u]);
- else
- if (colour[u] == 0)
- {
- dfs(u, v);
- ret[v] = min(ret[v], ret[u]);
- number = edges[v][i].number;
- if (enter[v] < ret[u]) {
- if (!bridges[number])
- k++;
- bridges[edges[v][i].number] = true;
- }
- }
- }
- colour[v] = 2;
- }
- int main()
- {
- ifstream in("bridges.in");
- ofstream out("bridges.out");
- int n, m;
- cin >> n >> m;
- edges.resize(n + 1);
- bridges = vector<bool>(m + 1, false);
- enter.resize(n + 1);
- ret.resize(n + 1);
- colour = vector<int>(n + 1, 0);
- k = 0;
- time_ = 0;
- int u, v;
- for (int i = 1; i <= m; i++)
- {
- cin >> u >> v;
- edges[u].push_back(edge(v, i));
- edges[v].push_back(edge(u, i));
- }
- for (int i = 1; i <= n; i++)
- if (colour[i] == 0)
- dfs(i, 0);
- cout << k << '\n';
- for (int i = 1; i <= m; i++)
- if (bridges[i])
- cout << i << ' ';
- return 0;
- }
Add Comment
Please, Sign In to add comment