CUBE-199: Sagittarius A*

#include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;

typedef long long int ll;
struct edge{
    int u,v,idx;
    ll w;
};

bool mycmp(edge a,edge b){
    return a.w > b.w;
}

int parent[100010];

int finds(int x){
    if(parent[x] == x){
        return x;
    }
    return parent[x] = finds(parent[x]);
}

void unions(int x,int y){
    int rx = finds(x);
    int ry = finds(y);
    parent[ry] = rx;
}

int main()
{
    for(int i = 0 ; i < 100010 ; i ++){
        parent[i] = i;
    }
    int n,m;
    scanf("%d %d",&n,&m);

    edge elist[m+1];
    bool echeck[m+1];
    for(int i = 1 ; i <= m ; i ++){
        int u,v;
        ll w;
        scanf("%d %d %lld",&u,&v,&w);
        if(u > v){ //swapping
            int temp = u;
            u = v;
            v = temp;
        }
        elist[i] = {u,v,i,w};
        echeck[i] = false;
    }
    sort(elist+1,elist+m+1,mycmp);
    set<pair<int,int> > myset;

    int cnte = 0;
    ll sum = 0;
    int ans[m];
    int aI = 0;
    //mst
    for(int i = 1 ; i <= m ; i ++){
        int u = elist[i].u;
        int v = elist[i].v;
        ll w = elist[i].w;
        int idx = elist[i].idx;

        if(finds(u) != finds(v)){
            unions(u,v);
            sum += w;
            cnte++;
            ans[aI++] = idx;
            echeck[i] = true;
            myset.insert({u,v});
        }
    }
//  return 0;
    int T;
    scanf("%d",&T);
    if(cnte != n - 1){ //not spanning
        printf("-1");
        return 0;
    }
    //building in greedy
    for(int i = 1 ; i <= m && cnte < n ; i ++){
        if(!echeck[i]){
            int u = elist[i].u;
            int v = elist[i].v;
            ll w = elist[i].w;
            int idx = elist[i].idx;
            if(myset.find({u,v}) == myset.end()){
                sum += w;
                cnte++;
                ans[aI++] = idx;
                echeck[i] = true;
                myset.insert({u,v});
            }
        }
    }



    if(cnte != n){
        printf("-1");
        return 0;
    }
    printf("%lld",sum);
    if(T == 2){
        printf("\n");
        for(int i = 0 ; i < aI ; i ++){
            printf("%d ",ans[i]);
        }
    }
    return 0;
}