Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define maxn 1005
- using namespace std;
- struct edge{
- int a, b, w;
- } G[maxn];
- vector<int> ans;
- int f[maxn];
- bool cmp ( edge x, edge y );
- void init( int n );
- int find ( int x );
- void U ( int x, int y );
- int main(){
- ios::sync_with_stdio( false );
- cin.tie(0);
- int n, m;
- while ( cin >>n >>m && (n||m) ){
- init(n);
- for ( int i=0; i<m; i++ )
- cin >>G[i].a >>G[i].b >>G[i].w;
- sort(G, G+m, cmp);
- for ( int i=0; i<m; i++ ){
- int a = G[i].a, b = G[i].b, w = G[i].w;
- if ( find(a) != find(b) ) U(a, b);
- else ans.emplace_back(w);
- }
- if ( ans.empty() ) cout <<"forest\n";
- else{
- for ( int i=0; i<ans.size()-1; i++ ) cout <<ans[i] <<' ';
- cout <<ans[ans.size()-1] <<'\n';
- }
- }
- return 0;
- }
- bool cmp ( edge x, edge y ){
- return x.w < y.w;
- }
- int find ( int x ){
- if ( f[x] == x ) return x;
- return f[x] = find(f[x]);
- }
- void U ( int x, int y ){
- f[find(x)] = find(y);
- }
- void init ( int n ){
- ans.clear();
- for ( int i=0; i<=n; i++ ) f[i] = i;
- }
Add Comment
Please, Sign In to add comment