HackerEarth Rebuild problem solution

In this HackerEarth Rebuild problem solution All roads of Byteland have been destroyed by a recent epic fight between good and evil. Unfortunately, the citizens need to get back to work and need to rebuild their road network.

There are n interesting points in the city, and there are m proposals for roads to build between the points. The i-th proposal is to build an undirected road between the ai-th point and the bi-th point with a cost of ci.

The city would like to build a set of roads such that it's possible to go from any one interesting point to any other interesting point through some series of built roads. They know that at least one such set of roads exists. If there are multiple sets of roads that satisfy the condition, they would like to find a set that minimizes the total cost of roads built. If there are multiple sets with minimum total cost, they will break ties in a process described in the next paragraph.

In the process of rebuilding, the city would also like to lower congestion in some points. More specifically, if there are multiple sets of roads with the same minimum cost, they would like to choose a set that minimizes the number of roads incident to the first interesting point (while keeping the cost minimum). If there are still ties, they would like to minimize the number of roads incident to the second interesting point (while keeping the cost and the number of roads incident to the first interesting point to be small). This continues on until the last interesting point.

More formally, we can say the degree sequence of a set of roads is the sequence {deg(1),deg(2),...,deg(n)}, where deg(i) is the number of roads incident to the i-th interesting point. Given two sets of roads R1,R2 that each connect all the points, we can say the city prefers R1 to R2 if R1's cost is strictly smaller than R2's cost, or R1 and R2 costs are equal and the degree sequence of R1 is lexicographically smaller than the degree sequence of R2.

Given n and the description of the m proposals of roads, print the minimum cost of a set of roads that connects the points and the degree sequence of that set of roads.

HackerEarth Rebuild problem solution.

import java.util.*;
import java.io.*;

public class Rebuild {
  static class Edge implements Comparable<Edge> {
    public int a,b,c;
    public Edge(int a, int b, int c) {
      this.a = a;
      this.b = b;
      this.c = c;
      if (this.a > this.b) {
        int t = this.a; this.a = this.b; this.b = t;
      }
    }
    
    public int compareTo(Edge other) {
      if (c != other.c) return c - other.c;
      if (a != other.a) return other.a - a;
      return other.b - b;
    }
  }
  
  public static int[] par, size;
  public static int find(int x) {
    return par[x] == x ? x : (par[x] = find(par[x]));
  }
  
  public static boolean join(int a, int b) {
    int x = find(a), y = find(b);
    if (x == y) return false;
    if (size[x] < size[y]) {
      int t = x; x = y; y = t;
    }
    
    size[x] += size[y];
    par[y] = x;
    return true;
  }
  
  public static void main (String[] args) {
    Scanner in = new Scanner (System.in);
    PrintWriter out = new PrintWriter (System.out, true);
    
    int t = in.nextInt();
    while(t-->0) {
      int n = in.nextInt(), m = in.nextInt();
      Edge[] e = new Edge[m];
      for (int i = 0; i < m; i++) {
        e[i] = new Edge(in.nextInt()-1, in.nextInt()-1, in.nextInt());
      }
      Arrays.sort(e);
      par = new int[n];
      size = new int[n];
      for (int i = 0; i < n; i++) {
        par[i] = i;
        size[i] = 1;
      }
      long totalcost = 0;
      int[] deg = new int[n];
      for (int i = 0; i < m; i++) {
        if (join(e[i].a, e[i].b)) {
          totalcost += e[i].c;
          deg[e[i].a]++;
          deg[e[i].b]++;
        }
      }
      out.println(totalcost);
      for (int i = 0; i < n; i++) {
        if (i != 0) out.print(" ");
        out.print(deg[i]);
      }
      out.println();
    }
    out.close();
    System.exit(0);
  }
}

Second solution

#include<bits/stdc++.h>
using namespace std;

const int nax = 1e5 + 5;
int par[nax], deg[nax];
int find(int a) { return a == par[a] ? a : par[a] = find(par[a]); }
void uni(int a, int b) { par[find(a)] = find(b); }

void te() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<vector<int>> w;
  while(m--) {
    int a, b, cost;
    scanf("%d%d%d", &a, &b, &cost);
    if(a > b) swap(a, b);
    w.push_back(vector<int>{cost,-a,-b});
  }
  sort(w.begin(), w.end());
  for(int i = 1; i <= n; ++i) {
    par[i] = i;
    deg[i] = 0;
  }
  long long total = 0;
  for(vector<int> edge : w) {
    int cost = edge[0];
    int a = -edge[1];
    int b = -edge[2];
    if(find(a) != find(b)) {
      uni(a, b);
      ++deg[a];
      ++deg[b];
      total += cost;
    }
  }
  printf("%lld\n", total);
  for(int i = 1; i <= n; ++i) printf("%d ", deg[i]);
  puts("");
}

int main() {
  int z;
  scanf("%d", &z);
  while(z--) te();
  return 0;
}