achulkov2

Untitled

Apr 12th, 2018
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.88 KB | None | 0 0
  1. //
  2. // main.cpp
  3. // 2.C
  4. //
  5. // Created by Andrey Chulkov on 7/29/15.
  6. // Copyright (c) 2015 Andrey Chulkov. All rights reserved.
  7. //
  8.  
  9. #include <iostream>
  10. #include <vector>
  11. #include <cmath>
  12. #include <map>
  13. #include <algorithm>
  14.  
  15. #define m_p make_pair
  16.  
  17. using namespace std;
  18. typedef pair<int, int> int_pair;
  19. int t = 0;
  20. vector<int> tin;
  21. vector<int> tout;
  22. vector<bool> used;
  23. vector<vector<int_pair>> graph;
  24. vector<int> bridges;
  25. map<pair<int, int>, int> edge_id;
  26. const int N = 1e5 + 7;
  27.  
  28. int dfs_fup(int v, int from) {
  29. int fup;
  30. used[v] = true;
  31. tin[v] = t;
  32. fup = tin[v];
  33. t += 1;
  34. for (auto u : graph[v]) {
  35. if (!used[u.first] && (u.second != from)) {
  36. int fup_u;
  37. fup_u = dfs_fup(u.first, u.second);
  38. fup = min(fup_u, fup);
  39. if (tin[v] < fup_u) {
  40. cout << v << " " << u.first << endl;
  41. bridges.push_back(edge_id[make_pair(v, u.first)]);
  42. }
  43. }
  44. else if (u.second != from) {
  45. fup = min(tin[u.first], fup);
  46. }
  47. }
  48. tout[v] = t;
  49. t += 1;
  50. return fup;
  51. }
  52.  
  53. int main() {
  54. int n, m;
  55. cin >> n >> m;
  56. graph.assign(n, vector<int_pair>());
  57. used.assign(n, false);
  58. tin.resize(n);
  59. tout.resize(n);
  60. for (int i = 0; i < m; i ++) {
  61. int b_i, e_i;
  62. cin >> b_i >> e_i;
  63. graph[b_i - 1].push_back(m_p(e_i - 1, i));
  64. graph[e_i - 1].push_back(m_p(b_i - 1, i));
  65. edge_id[m_p(b_i - 1, e_i - 1)] = i + 1;
  66. edge_id[m_p(e_i - 1, b_i - 1)] = i + 1;
  67. }
  68. for (int v = 0; v < n; v ++) {
  69. if (!used[v]) {
  70. dfs_fup(v, N);
  71. }
  72. }
  73. int k;
  74. k = (int) bridges.size();
  75. cout << k << endl;
  76. sort(bridges.begin(), bridges.end());
  77. for (int i = 0; i < k; i ++) {
  78. cout << bridges[i] << endl;
  79. }
  80. return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment