Red Huang

Red Huang

uva 11857

Find the maximum edge in MST

SubmissionErr Another solution to this problem (I don't know if this code has any errors because the platform is no longer available)

//====================================================================||  
//                                                                    ||  
//                                                                    ||  
//                         Author : GCA                               ||  
//                  6AE7EE02212D47DAD26C32C0FE829006                  ||  
//====================================================================||  
#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <cmath>  
#include <climits>  
#include <vector>  
#include <set>  
#include <map>  
#include <queue>  
#include <cctype>  
#include <utility>  
using namespace std;  
#ifdef ONLINE\_JUDGE  
#define ll "%lld"  
#else  
#define ll "%I64d"  
#endif  
typedef unsigned int uint;  
typedef long long int Int;  
#define Set(a,s) memset(a,s,sizeof(a))  
#define Write(w) freopen(w,"w",stdout)  
#define Read(r) freopen(r,"r",stdin)  
#define Pln() printf("\\n")  
#define I\_de(x,n)for(int i=0;i<n;i++)printf("%d ",x\[i\]);Pln()  
#define De(x)printf(#x"%d\\n",x)  
#define For(i,x)for(int i=0;i<x;i++)  
#define CON(x,y) x##y  
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\  
    printf("%d ",dp\[htx\]\[hty\]);}Pln();}  
#define M 1000005  
#define PII pair<int,int\>  
#define PB push\_back  
#define oo INT\_MAX  
#define Set\_oo 0x3f  
#define Is\_debug true  
#define debug(...) if(Is\_debug)printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)  
#define FOR(it,c) for(\_\_typeof((c).begin()) it=(c).begin();it!=(c).end();it++)  
#define eps 1e-6  
bool xdy(double x,double y){return x>y+eps;}  
bool xddy(double x,double y){return x>y-eps;}  
bool xcy(double x,double y){return x<y-eps;}  
bool xcdy(double x,double y){return x<y+eps;}  
int min3(int x,int y,int z){  
    int tmp=min(x,y);  
    return min(tmp,z);  
}  
int max3(int x,int y,int z){  
    int tmp=max(x,y);  
    return max(tmp,z);  
}  
struct edge{  
    int x,y,w;  
}edges\[M\];  
int n,m;  
int p\[M\];  
int rank\[M\];  
bool cmp(edge a,edge b){  
    return a.w<b.w;  
}  
void init(){  
    for(int i=0;i<n;i++){  
        rank\[i\]=0;  
        p\[i\]=i;  
    }  
}  
int getf(int x){  
    if(x!=p\[x\])p\[x\]=getf(p\[x\]);  
    return p\[x\];  
}  
void \_union(int x,int y){  
  
    if(rank\[x\]>rank\[y\])p\[y\]=x;  
    else{  
        p\[x\]=y;  
        if(rank\[x\]==rank\[y\])rank\[y\]++;  
    }  
  
}  
void solve(){  
    sort(edges,edges+m,cmp);  
    int mx=0;  
    int cm=0;  
    for(int i=0;i<m;i++){  
        int x=edges\[i\].x;  
        int y=edges\[i\].y;  
        int w=edges\[i\].w;  
        int fx=getf(x);  
        int fy=getf(y);  
        if(fx!=fy){  
            \_union(fx,fy);  
            cm++;  
            mx=max(mx,w);  
        }  
    }  
    if(cm+1<n)printf("IMPOSSIBLE\\n");  
    else printf("%d\\n",mx);  
}  
int main() {  
    ios\_base::sync\_with\_stdio(0);  
    while(~scanf("%d%d",&n,&m)&&n+m){  
        init();  
        for(int i=0;i<m;i++){  
            scanf("%d%d%d",&edges\[i\].x,&edges\[i\].y,&edges\[i\].w);  
        }  
        solve();  
    }  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
}  

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.