Guest User

Untitled

a guest
Jul 11th, 2018
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<map>
  5. using namespace std;
  6.  
  7. typedef long long int ll;
  8. #define X first
  9. #define Y second
  10. #define mp make_pair
  11.  
  12. const int N = 1e3;
  13. int n, m, s;
  14. int pred [N], mark [N];
  15. vector<pair<pair<ll, int>, pair<int, int> > > list;
  16.  
  17. void makeSet (int vertex)
  18. {
  19.     pred [vertex] = vertex;
  20. }
  21.  
  22. int givePred (int vertex)
  23. {
  24.     if (pred[vertex] != vertex)
  25.         pred [vertex] = givePred (pred[vertex]);
  26.  
  27.     return pred [vertex];
  28. }
  29.  
  30. void unionSet (int vertex1, int vertex2)
  31. {
  32.     int x = givePred(vertex1);
  33.     int y = givePred(vertex2);
  34.  
  35.     pred [x] = y;
  36. }
  37.  
  38. int main ()
  39. {
  40. #ifndef ONLINE_JUDGE
  41.     freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  42. #endif
  43.  
  44.     scanf("%d%d%lld", &n, &m, &s);
  45.     for (int i = 0; i < m; i++)
  46.     {
  47.         int v1, v2;
  48.         ll w;
  49.         scanf("%d%d%lld", &v1, &v2, &w);
  50.         list.push_back(mp(mp(w, i), mp(v1, v2)));
  51.     }
  52.  
  53.     sort(list.begin(), list.begin());
  54.  
  55.     for (int i = 0; i < (int)list.size(); i++)
  56.     {
  57.         int p1 = givePred(list[i].Y.X);
  58.         int p2 = givePred(list[i].Y.Y);
  59.  
  60.         if (p1 != p2)
  61.         {
  62.             unionSet(p1, p2);
  63.             mark [list[i].X.Y] = 1;
  64.         }
  65.     }
  66.  
  67.     vector<int> ans;
  68.     for (int i = 0; i < m; i++)
  69.         if (!mark[i])
  70.             ans.push_back(i + 1);
  71.  
  72.     printf("%d\n", ans.size());
  73.     for (int i = 0; i < (int)ans.size(); i++)
  74.         printf("%d ", ans[i]);
  75.  
  76.     return 0;
  77. }
Add Comment
Please, Sign In to add comment