Advertisement
Guest User

Untitled

a guest
Nov 19th, 2019
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.91 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. vector<int>dsu;
  7.  
  8. void MakeSet(int n) {
  9. dsu.resize(n);
  10. for (int i = 0; i < n; i++) {
  11. dsu[i] = i;
  12. }
  13. }
  14.  
  15. int Find(int x) {
  16. return (dsu[x] == x) ? x : dsu[x] = Find(dsu[x]);
  17. }
  18.  
  19. void Union(int a, int b) {
  20. a = Find(a);
  21. b = Find(b);
  22. if (rand() % 2) {
  23. swap(a, b);
  24. }
  25. dsu[a] = b;
  26. }
  27.  
  28. int main() {
  29. ifstream fin("maxincycle.in");
  30. ofstream fout("maxincycle.out");
  31. int n, m, a, b;
  32. fin >> n >> m;
  33. MakeSet(n);
  34. vector<pair<int, int>>v;
  35. vector<int>answers;
  36. for (int i = 0; i < m; i++) {
  37. fin >> a >> b;
  38. v.push_back({ a - 1, b - 1 });
  39. }
  40. for (int i = 0; i < v.size(); ++i) {
  41. if (Find(v[i].first) != Find(v[i].second)) {
  42. Union(v[i].first, v[i].second);
  43. answers.push_back(i);
  44. }
  45. }
  46. fout << answers.size() << endl;
  47. for (int i = 0; i < answers.size(); i++) {
  48. fout << answers[i] + 1 << " ";
  49. }
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement