Advertisement
Guest User

Untitled

a guest
Jan 26th, 2020
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.70 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <map>
  6. #include <set>
  7.  
  8. #define forn(i, n) for(int i = 1; i <= n; ++i)
  9. #define MAX 20001
  10.  
  11. using namespace std;
  12.  
  13. vector<vector<int>>graph(MAX);
  14. set <int> b;
  15. map<pair<int, int>, int> table; //чтобы в отсортированном виде
  16.  
  17. int time[MAX], min_time[MAX];
  18.  
  19. int n, m, T;
  20.  
  21. #include <cassert>
  22.  
  23. /** Begin fast allocation */
  24. const int MAX_MEM = 1e8;
  25. int mpos = 0;
  26. char mem[MAX_MEM];
  27. inline void * operator new ( size_t n ) {
  28. assert((mpos += n) <= MAX_MEM);
  29. return (void *)(mem + mpos - n);
  30. }
  31. inline void operator delete ( void * ) noexcept { } // must have!
  32. /** End fast allocation */
  33.  
  34. void dfs (int v, int p) {
  35. time[v] = min_time[v] = ++T;
  36. for (int x : graph[v])
  37. if (x != p) {
  38. if (time[x] == 0) { // древесное ребро
  39. dfs(x, v);
  40. if (min_time[x] > time[v]) { // мост!
  41. b.insert(table[{v, x}]);
  42. }
  43. min_time[v] = min(min_time[v], min_time[x]);
  44. } else { // обратное или двойственное ему ребро в другую сторону
  45. min_time [v] = min(min_time[v], time [x]);
  46. }
  47. }
  48. }
  49.  
  50.  
  51. int main() {
  52. ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  53. cin >> n >> m;
  54.  
  55. int u, v;
  56. forn(i, m) {
  57. cin >> v >> u;
  58. graph[v].push_back(u);
  59. graph[u].push_back(v);
  60. table[{v, u}] = i;
  61. }
  62.  
  63. T = 0;
  64. forn(i, n) if (!time[i]) dfs(i, 0);
  65.  
  66. cout << b.size() << "\n";
  67. for (auto i = b.begin(); i != b.end(); i++) {
  68. cout << *i << "\n";
  69. }
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement