Advertisement
Guest User

Untitled

a guest
Dec 15th, 2018
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.82 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define f first
  3. #define s second
  4. using namespace std;
  5. int n, m, B = 0, q, pro[20001], gaa[20001], ff, i;
  6. vector<pair<int, int>> aaa;
  7. vector<pair<int, int>> deeed;
  8. vector<vector<int>> zokeri;
  9. vector<bool> ystal(20001, 0);
  10. vector<int> konec;
  11. void dfs (int xi, int ggvp)
  12. {
  13. ystal[xi] = 1;
  14. pro[xi] = q++;
  15. gaa[xi] = q++;
  16. for (i = 0; i < zokeri[xi].size(); i++)
  17. {
  18. ff = zokeri[xi][i];
  19. if (ff == ggvp)
  20. continue;
  21. if (ystal[ff])
  22. gaa[xi] = min(gaa[xi], pro[ff]);
  23. else
  24. {
  25. dfs (ff, xi);
  26. gaa[xi] = min(gaa[xi], gaa[ff]);
  27. if (gaa[ff] > pro[xi])
  28. {
  29. B++;
  30. deeed.push_back({xi, ff});
  31. }
  32. }
  33. }
  34. }
  35. int main()
  36. {
  37. int b, e, j, glhf, niay;
  38. cin >> n >> m;
  39. aaa.resize(m);
  40. zokeri.resize(n);
  41. for(i = 0; i < m; i++)
  42. {
  43. cin >> b >> e;
  44. zokeri[b - 1].push_back(e - 1);
  45. zokeri[e - 1].push_back(b - 1);
  46. aaa[i].f = b - 1;
  47. aaa[i].s = e - 1;
  48. }
  49. for (i = 0; i < n; i++)
  50. {
  51. if (!ystal[i])
  52. dfs (i, -1);
  53. }
  54. for(i = 0; i < deeed.size(); i++)
  55. {
  56. glhf = 0, niay = 0;
  57. for (j = 0; j < m; j++)
  58. {
  59. if (((deeed[i].f == aaa[j].f) and (deeed[i].s == aaa[j].s)) or ((deeed[i].f == aaa[j].s) and (deeed[i].s == aaa[j].f)))
  60. {
  61. glhf++;
  62. niay = j+1;
  63. }
  64. }
  65. if(glhf == 1)
  66. konec.push_back(niay);
  67. else
  68. B--;
  69. }
  70. cout << B << "\n";
  71. sort(konec.begin(), konec.end());
  72. for(auto N : konec)
  73. cout << N << " ";
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement