Advertisement
Guest User

Untitled

a guest
Nov 14th, 2018
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.91 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <algorithm>
  5. #include <map>
  6.  
  7.  
  8. using namespace std;
  9.  
  10. pair <int, int> make_edges(int v1, int v2) {
  11.     if (v1 > v2)
  12.         return make_pair(v2, v1);
  13.     return make_pair(v1, v2);
  14. }
  15.  
  16. 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) {
  17.     used[v] = true;
  18.     tin[v] = timer++;
  19.     up[v] = tin[v];
  20.     for (int u = 0; u < graph[v].size(); ++u) {
  21.         if (!used[graph[v][u]]) {
  22.             find_bridges(graph, edges, result, graph[v][u], used, tin, up, timer, v);
  23.             up[v] = min(up[v], up[graph[v][u]]);
  24.         }
  25.         else if (graph[v][u] != p) {
  26.             up[v] = min(up[v], tin[graph[v][u]]);
  27.         }
  28.     }
  29.     if ((p != -1) && (tin[v] == up[v]) && (edges[make_edges(v, p)] != -1))
  30.         result.insert(edges[make_edges(v, p)]);
  31. }
  32.  
  33. void bridges(vector<vector<int>>& graph, map<pair<int, int>, int>& edges, set<int>& result) {
  34.     vector <bool> used;
  35.     int timer = 0;
  36.     vector<int> tin;
  37.     vector<int> up;
  38.     used.resize(graph.size());
  39.     tin.resize(graph.size());
  40.     up.resize(graph.size());
  41.     for (int i = 0; i < graph.size(); ++i) {
  42.         find_bridges(graph, edges, result, i, used, tin, up, timer);
  43.     }
  44. }
  45. int main() {
  46.     int n, m;
  47.     cin >> n >> m;
  48.     vector < vector<int>> graph(n);
  49.     map<pair<int, int>, int> edges;
  50.     for (int i = 0; i < m; ++i) {
  51.         int firstV, secondV;
  52.         cin >> firstV >> secondV;
  53.         if (edges.find(make_edges(firstV - 1, secondV - 1)) == edges.end())
  54.             edges[make_edges(firstV - 1, secondV - 1)] = i + 1;
  55.         else
  56.             edges[make_edges(firstV - 1, secondV - 1)] = -1;
  57.         graph[firstV - 1].push_back(secondV - 1);
  58.         graph[secondV - 1].push_back(firstV - 1);
  59.     }
  60.     set<int> result;
  61.     bridges(graph, edges, result);
  62.     cout << result.size() << endl;
  63.     for (std::set<int>::iterator i = result.begin(); i != result.end(); ++i)
  64.         cout << *i << endl;
  65.     //system("pause");
  66.     return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement