Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <set>
- #include <algorithm>
- #include <map>
- using namespace std;
- pair <int, int> make_edges(int v1, int v2) {
- if (v1 > v2)
- return make_pair(v2, v1);
- return make_pair(v1, v2);
- }
- void find_bridges(vector<vector<int>>& graph, map<pair<int, int>, int>& edges, set<int>& result, int v, vector <bool>& used, vector <int>& tin, vector <int>& up, int timer, int p = -1) {
- used[v] = true;
- tin[v] = timer++;
- up[v] = tin[v];
- for (int u = 0; u < graph[v].size(); ++u) {
- if (!used[graph[v][u]]) {
- find_bridges(graph, edges, result, graph[v][u], used, tin, up, timer, v);
- up[v] = min(up[v], up[graph[v][u]]);
- }
- else if (graph[v][u] != p) {
- up[v] = min(up[v], tin[graph[v][u]]);
- }
- }
- if ((p != -1) && (tin[v] == up[v]) && (edges[make_edges(v, p)] != -1))
- result.insert(edges[make_edges(v, p)]);
- }
- void bridges(vector<vector<int>>& graph, map<pair<int, int>, int>& edges, set<int>& result) {
- vector <bool> used;
- int timer = 0;
- vector<int> tin;
- vector<int> up;
- used.resize(graph.size());
- tin.resize(graph.size());
- up.resize(graph.size());
- for (int i = 0; i < graph.size(); ++i) {
- find_bridges(graph, edges, result, i, used, tin, up, timer);
- }
- }
- int main() {
- int n, m;
- cin >> n >> m;
- vector < vector<int>> graph(n);
- map<pair<int, int>, int> edges;
- for (int i = 0; i < m; ++i) {
- int firstV, secondV;
- cin >> firstV >> secondV;
- if (edges.find(make_edges(firstV - 1, secondV - 1)) == edges.end())
- edges[make_edges(firstV - 1, secondV - 1)] = i + 1;
- else
- edges[make_edges(firstV - 1, secondV - 1)] = -1;
- graph[firstV - 1].push_back(secondV - 1);
- graph[secondV - 1].push_back(firstV - 1);
- }
- set<int> result;
- bridges(graph, edges, result);
- cout << result.size() << endl;
- for (std::set<int>::iterator i = result.begin(); i != result.end(); ++i)
- cout << *i << endl;
- //system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement