Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include<algorithm>
- #include<map>
- using namespace std;
- typedef long long int ll;
- #define X first
- #define Y second
- #define mp make_pair
- const int N = 1e3;
- int n, m, s;
- int pred [N], mark [N];
- vector<pair<pair<ll, int>, pair<int, int> > > list;
- void makeSet (int vertex)
- {
- pred [vertex] = vertex;
- }
- int givePred (int vertex)
- {
- if (pred[vertex] != vertex)
- pred [vertex] = givePred (pred[vertex]);
- return pred [vertex];
- }
- void unionSet (int vertex1, int vertex2)
- {
- int x = givePred(vertex1);
- int y = givePred(vertex2);
- pred [x] = y;
- }
- int main ()
- {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
- #endif
- scanf("%d%d%lld", &n, &m, &s);
- for (int i = 0; i < m; i++)
- {
- int v1, v2;
- ll w;
- scanf("%d%d%lld", &v1, &v2, &w);
- list.push_back(mp(mp(w, i), mp(v1, v2)));
- }
- sort(list.begin(), list.begin());
- for (int i = 0; i < (int)list.size(); i++)
- {
- int p1 = givePred(list[i].Y.X);
- int p2 = givePred(list[i].Y.Y);
- if (p1 != p2)
- {
- unionSet(p1, p2);
- mark [list[i].X.Y] = 1;
- }
- }
- vector<int> ans;
- for (int i = 0; i < m; i++)
- if (!mark[i])
- ans.push_back(i + 1);
- printf("%d\n", ans.size());
- for (int i = 0; i < (int)ans.size(); i++)
- printf("%d ", ans[i]);
- return 0;
- }
Add Comment
Please, Sign In to add comment