Advertisement
illfate

Untitled

Mar 17th, 2019
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.27 KB | None | 0 0
  1. void Graph::brigdeUtil(int u, std::deque<bool>& visited, vector<int>& disc, vector<int>& low, vector<int>& parent) {
  2. static int time = 0;
  3. int children = 0;
  4. visited[u] = true;
  5. disc[u] = low[u] = ++time;
  6. for (auto i = graph[u].begin(); i != graph[u].end(); ++i) {
  7. int v = *i;
  8. if (!visited[v]) {
  9. children++;
  10. parent[v] = u;
  11. brigdeUtil(v, visited, disc, low, parent);
  12. low[u] = std::min(low[u], low[v]);
  13. if (low[v] > disc[u]) {
  14. auto it = counter.find(std::make_pair(u, v));
  15. auto it2 = counter.find(std::make_pair(v, u));
  16. if (it != counter.end()) {
  17. set_of_roads.insert(this->counter.at(std::make_pair(u, v)));
  18. }
  19. else if (it2 != counter.end()) {
  20. set_of_roads.insert(this->counter.at(std::make_pair(v, u)));
  21. }
  22. }
  23. if (parent[u] == NIL && children > 1)
  24. set_of_points.insert(u);
  25.  
  26.  
  27. if (parent[u] != NIL && low[v] >= disc[u])
  28. set_of_points.insert(u);
  29. }
  30. else if (v != parent[u]) {
  31. low[u] = std::min(low[u], disc[v]);
  32. }
  33. }
  34. }
  35. void Graph::get() {
  36. std::cout << set_of_roads.size() << std::endl;
  37. for (const auto& x : set_of_roads) {
  38. std::cout << x << std::endl;
  39. }
  40. std::cout << set_of_points.size() << std::endl;
  41. for (const auto& x : set_of_points) {
  42. std::cout << x << std::endl;
  43. }
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement