Guest User

Untitled

a guest
Dec 12th, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.96 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define maxn 1005
  3. using namespace std;
  4. struct edge{
  5. int a, b, w;
  6. } G[maxn];
  7. vector<int> ans;
  8. int f[maxn];
  9. bool cmp ( edge x, edge y );
  10. void init( int n );
  11. int find ( int x );
  12. void U ( int x, int y );
  13. int main(){
  14. ios::sync_with_stdio( false );
  15. cin.tie(0);
  16. int n, m;
  17. while ( cin >>n >>m && (n||m) ){
  18. init(n);
  19. for ( int i=0; i<m; i++ )
  20. cin >>G[i].a >>G[i].b >>G[i].w;
  21. sort(G, G+m, cmp);
  22. for ( int i=0; i<m; i++ ){
  23. int a = G[i].a, b = G[i].b, w = G[i].w;
  24. if ( find(a) != find(b) ) U(a, b);
  25. else ans.emplace_back(w);
  26. }
  27. if ( ans.empty() ) cout <<"forest\n";
  28. else{
  29. for ( int i=0; i<ans.size()-1; i++ ) cout <<ans[i] <<' ';
  30. cout <<ans[ans.size()-1] <<'\n';
  31. }
  32. }
  33. return 0;
  34. }
  35. bool cmp ( edge x, edge y ){
  36. return x.w < y.w;
  37. }
  38. int find ( int x ){
  39. if ( f[x] == x ) return x;
  40. return f[x] = find(f[x]);
  41. }
  42. void U ( int x, int y ){
  43. f[find(x)] = find(y);
  44. }
  45. void init ( int n ){
  46. ans.clear();
  47. for ( int i=0; i<=n; i++ ) f[i] = i;
  48. }
Add Comment
Please, Sign In to add comment