HackerRank The Value of Friendship Solution

In this post, we will solve HackerRank The Value of Friendship Problem Solution.

You’re researching friendships between groups of n new college students where each student is distinctly numbered from 1 to n. At the beginning of the semester, no student knew any other student; instead, they met and formed individual friendships as the semester went on. The friendships between students are:

Bidirectional. If student a is friends with student b, then student b is also friends with student a.
Transitive. If student a is friends with student b and student bis friends with student c. then student a is friends with student c. In other words, two students are considered to be friends even if they are only indirectly linked through a network of mutual (i.e., directly connected) friends.

The purpose of your research is to find the maximum total value of a group’s friendships, denoted by total. Each time a direct friendship forms between two students, you sum the number of friends that each of the n students has and add the sum to total.
You are given q queries, where each query is in the form of an unordered list of m distinct direct friendships between ŉ students. For each query, find the maximum value of total among all possible orderings of formed friendships and print it on a new line.

Input Format
The first line contains an integer, q, denoting the number of queries. The subsequent lines describe each query in the following format:

The first line contains two space-separated integers describing the respective values of n (the number of students) and m (the number of distinct direct friendships).
Each of the m subsequent lines contains two space-separated integers describing the respective values of x and y (where x + y) describing a friendship between student and student y.

Output Format

For each query, print the maximum value of total on a new line.

Sample Input 0

HackerRank The Value of Friendship Problem Solution

The Value of Friendship C Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _lnode{
  int x;
  int w;
  struct _lnode *next;
} lnode;
void dfs(int x);
void clean_table();
void insert_edge(int x,int y,int w);
void sort_a(int*a,int size);
void merge(int*a,int*left,int*right,int left_size, int right_size);
int g[100000],trace[100000],c;
lnode *table[100000]={0};

int main(){
  int q,n,m,x,y,g_size,i,j;
  long long ans,sum;
  scanf("%d",&q);
  while(q--){
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
      scanf("%d%d",&x,&y);
      insert_edge(x-1,y-1,0);
    }
    memset(trace,0,sizeof(trace));
    for(i=g_size=0;i<n;i++)
      if(!trace[i]){
        c=0;
        dfs(i);
        g[g_size++]=c;
      }
    sort_a(g,g_size);
    for(i=g_size-1,ans=sum=x=0;i>=0;sum+=j*(long long)(j+1),x+=g[i]-1,i--)
      for(j=0;j<g[i]-1;j++)
        ans+=(j+1)*(long long)(j+2)+sum;
    ans+=sum*(m-x);
    printf("%lld\n",ans);
    clean_table();
  }
  return 0;
}
void dfs(int x){
  lnode *p;
  trace[x]=1;
  c++;
  for(p=table[x];p;p=p->next)
    if(!trace[p->x])
      dfs(p->x);
  return;
}
void clean_table(){
  int i;
  lnode *p,*pp;
  for(i=0;i<100000;i++)
    if(table[i]){
      p=table[i];
      while(p){
        pp=p->next;
        free(p);
        p=pp;
      }
      table[i]=NULL;
    }
  return;
}
void insert_edge(int x,int y,int w){
  lnode *t=malloc(sizeof(lnode));
  t->x=y;
  t->w=w;
  t->next=table[x];
  table[x]=t;
  t=malloc(sizeof(lnode));
  t->x=x;
  t->w=w;
  t->next=table[y];
  table[y]=t;
  return;
}
void sort_a(int*a,int size)
{
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int *left,*right;
  left=(int*)malloc(m*sizeof(int));
  right=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++)
    left[i]=a[i];
  for(i=0;i<size-m;i++)
    right[i]=a[i+m];
  sort_a(left,m);
  sort_a(right,size-m);
  merge(a,left,right,m,size-m);
  free(left);
  free(right);
  return;
}
void merge(int*a,int*left,int*right,int left_size, int right_size) {
    int i = 0, j = 0;
    while (i < left_size|| j < right_size) {
        if (i == left_size) {
            a[i+j] = right[j];
            j++;
        } else if (j == right_size) {
            a[i+j] = left[i];
            i++;
        } else if (left[i] <= right[j]) {
            a[i+j] = left[i];
            i++;                
        } else {
            a[i+j] = right[j];
            j++;
        }
    }
    return;
}

The Value of Friendship C++ Solution

#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define each(it,o) for(auto it= (o).begin(); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define inrep int t;cin>>t; while(t--)
using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii > vpii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll > vpll;
typedef vector<string> vs;
typedef long double ld;

template<typename T> ostream& operator<< ( ostream &o,vector<T> v ) {
    if ( v.size() >0 )
        o<<v[0];
    for ( unsigned   i=1; i<v.size(); i++ )
        o<<" "<<v[i];
    return o<<endl;
}
template<typename U,typename V> ostream& operator<< ( ostream &o,pair<U,V> p ) {
    return o<<"("<<p.first<<", "<<p.second<<") ";
}
template<typename T> istream& operator>> ( istream &in,vector<T> &v ) {

    for ( unsigned   i=0; i<v.size(); i++ )
        in>>v[i];
    return in;
}
#define gc getchar_unlocked
void scan ( int &x ) {
    int c = gc();
    x = 0;
    for ( ; ( c<48 || c>57 ); c = gc() );
    for ( ; c>47 && c<58; c = gc() ) {
        x = ( x << 1 ) + ( x << 3 ) + c - 48;
    }
}
vector<bool> vis;
vector<vi> adj;
int cntComp ( int x ) {
    int su=1;
    vis[x]=1;
    for ( int y: adj[x] ) {
        if ( !vis[y] ) su+=cntComp ( y );
    }
    return su;
}
int main() {
    int t;
    scan ( t );
    vll prec(100005);
    reu(i,1,100005){
     prec[i]=prec[i-1]+(ll)i*(i+1);   
    }
    while ( t-- ) {
        int n,m;
        scan ( n );
        scan ( m );
        adj=vector<vi> ( n );
        rep ( i,m ) {
            int u,v;
            scan ( u );
            scan ( v );
            u--;
            v--;
            adj[u].push_back(v); adj[v].push_back(u);

        }
        vi compSize;
        vis=vector<bool> ( n );
        rep ( i,n ) {
            if ( !vis[i] ) {
                compSize.push_back ( cntComp ( i ) );
            }
        }
        sort ( all ( compSize), greater<int>( ) );
        int used=0;
        ll su=0;
        ll comps=0;
        for ( int x: compSize ) {
            used+= ( x-1 );
            su+= prec[x-1]+ll ( x-1 ) *comps;
            comps+=(ll)x*(x-1);
        }
        su+= ( ll ) ( m-used ) *comps;
        printf ( "%lld\n", su );

    }
}
// kate: indent-mode cstyle; indent-width 4; replace-tabs on;

The Value of Friendship C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {

    static void Main(String[] args) {
        int t = Convert.ToInt32(Console.ReadLine());
        for(int a0 = 0; a0 < t; a0++){
            string[] tokens_n = Console.ReadLine().Split(' ');
            int n = Convert.ToInt32(tokens_n[0]);
            int m = Convert.ToInt32(tokens_n[1]);
                Query q = new Query();
            for (int a1 = 0; a1 < m; a1++)
            {
                string[] tokens_x = Console.ReadLine().Split(' ');
                int x = Convert.ToInt32(tokens_x[0]);
                int y = Convert.ToInt32(tokens_x[1]);
                q.Add(x, y);
            }
            var res = q.Exec();
            Console.WriteLine(res);
        }
    }
}

class Query
{
    Graph graph = new Graph();

    public System.Numerics.BigInteger Exec()
    {
        var graphs = GraphHelper.GetSouvisleGrafy(graph);//.Dump();

        System.Numerics.BigInteger total = 0;
        System.Numerics.BigInteger topLevelTotal = 0;



        foreach (var g in graphs.OrderByDescending(x => x.vertices.Count))
        {
            System.Numerics.BigInteger subTotal = 0;
            for (int i = 0; i <= g.vertices.Count - 2; i++)
            {
                System.Numerics.BigInteger si = i + 1;
                subTotal += ValueOfFrendAtLevel(i);
                total += topLevelTotal;
                //total += i + 1
               // if (total > long.MaxValue) throw new Exception();
            }
            // added others
            total += subTotal;
            topLevelTotal += ValueOfFrendAtLevel(g.vertices.Count - 2);
        }

        // add total levels(doubled relations ships)
        foreach (var g in graphs)
        {
            for (int i = 0; i <= g.edges.Count - g.vertices.Count; i++)
            {
                total += topLevelTotal;
            }
        }

        return total;

    }
    
    HashSet<long> duplitates = new HashSet<long>();

    public void Add(int a, int b)
    {
        graph.AddEdge(a, b);
        
        long key = Edge.GetEdgeKey(a, b);
        if (duplitates.Contains(key)) throw new Exception();
        duplitates.Add(key);
    }

    private System.Numerics.BigInteger ValueOfFrendAtLevel(System.Numerics.BigInteger level)
    {
        return (level + 1) * (level + 2);
    }


}

public static class GraphHelper
{
    public static List<Graph> GetSouvisleGrafy(Graph original)
    {
        List<Graph> ret = new List<Graph>();

        // abych dokazal vyhodnotit jiz prosle cesty v grafu
        HashSet<long> traversedPaths = new HashSet<long>();

        // abych dokazal nesouvisle gragy
        HashSet<int> traversedVertices = new HashSet<int>();

        foreach (int vertex in original.vertices.Keys)
        {
            // skip traversed 
            if (traversedVertices.Contains(vertex)) continue;

            Graph g = new Graph();
            ret.Add(g);

            TraverseEdges(original, g, vertex, traversedVertices, traversedPaths);
        }

        return ret;
    }

    private static void TraverseEdges(Graph original, Graph graph, int vertexX, HashSet<int> traversedVertices, HashSet<long> traversedPath)
    {
        // already used
        traversedVertices.Add(vertexX);

        var vertex = original.vertices[vertexX];

        foreach (var oppositVertex in vertex.Edges)
        {
            //    if(backPath != oppositVertex) graph.AddEdge(vertexX, oppositVertex);

            // tohle se da vylepsit, A a B kotrolovat na vertexX
            //  int oppositVertex;
            //if (edge.VertexA == vertexX) oppositVertex = edge.VertexB; else oppositVertex = edge.VertexA;

            // do tohohle bodu jsem jeste nesel, tak ho taky projdu

            long edgeKey = Edge.GetEdgeKey(vertexX, oppositVertex);

            if (!traversedPath.Contains(edgeKey))
            {
                traversedPath.Add(edgeKey);
                graph.AddEdge(vertexX, oppositVertex);
                TraverseEdges(original, graph, oppositVertex, traversedVertices, traversedPath);
            }
        }
    }
}



public class Graph
{
    public readonly Dictionary<int, Vertex> vertices = new Dictionary<int, Vertex>();
    public readonly List<Edge> edges = new List<Edge>();

    public void AddEdge(int a, int b)
    {
        Vertex vertexA = this.GetOrCreateVertex(a);
        Vertex vertexB = this.GetOrCreateVertex(b);

        Edge edg = new Edge(a, b);
        vertexA.Edges.Add(b);
        vertexB.Edges.Add(a);
        edges.Add(edg);
    }

    private Vertex GetOrCreateVertex(int x)
    {
        Vertex ret;
        if (this.vertices.TryGetValue(x, out ret)) return ret;

        ret = new Vertex();
        vertices.Add(x, ret);
        return ret;
    }

    public override string ToString()
    {
        return $"Graph Edges:{this.edges.Count}, Vertices:{this.vertices.Count}";
    }
}

public class Edge
{
    public Edge(int vertexA, int vertexB)
    {
        this.VertexA = vertexA;
        this.VertexB = vertexB;
    }
    public int VertexA { get; set; }
    public int VertexB { get; set; }

    public static long GetEdgeKey(int a, int b)
    {
        if (a > b)
        {
            return (((long)a) << 32) | b;
        }
        return (((long)b) << 32) | a;
    }

    public override string ToString()
    {
        return $"Edge A:{VertexA}, B:{VertexB}";
    }
}

public class Vertex
{
    public HashSet<int> Edges = new HashSet<int>();

    public override string ToString()
    {
        return $"Vertex Edges:{Edges.Count}";
    }
}
///aaaaaaaaaaaaaaaaaaaaaaaaaaa

The Value of Friendship Java Solution

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int a0 = 0; a0 < t; a0++){
            int n = in.nextInt();
            int m = in.nextInt();

            DisjointSets friendGroups = new DisjointSets(n);
            
            for(int a1 = 0; a1 < m; a1++){
                int x = in.nextInt();
                int y = in.nextInt();
                // your code goes here
                friendGroups.union(x - 1, y - 1);
            }
            
            List<Integer> groupSizes = friendGroups.setSizes();
            Collections.sort(groupSizes, Comparator.reverseOrder());

            long[] extra = new long[m];
            int idx = 0;
            for (int size : groupSizes) {
                for (int i = 1; i < size; i++) {
                    extra[idx++] = i;
                }
            }
            
            long totalFriendship = 0;
            long currentFriendship = 0;
            for (int i = 0; i < m; i++) {
                currentFriendship += 2L * extra[i];
                totalFriendship += currentFriendship;
            }
            System.out.println(totalFriendship);
        }
    }
    
    private static class DisjointSets {
        private int[] parent;
        private int[] size;
        
        public DisjointSets(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        
        public void union(int a, int b) {
            int p = find(a);
            int q = find(b);
            if (p == q)
                return;
            if (size[p] < size[q]) {
                parent[p] = q;
                size[q] += size[p];
            }
            else {
                parent[q] = p;
                size[p] += size[q];
            }
        }
        
        public int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        
        public List<Integer> setSizes() {
            Set<Integer> sets = new HashSet<>();
            for (int x : parent)
                sets.add(find(x));
            List<Integer> sizes = new ArrayList<>();
            for (int x : sets)
                sizes.add(size[x]);
            return sizes;
        }
    }
}

The Value of Friendship JavaScript Solution

function Edge(a, b) {
    this.a = a;
    this.b = b;
}

function DisjointSet(N) {
    this.N = N;
    this.numSets = N;
    this.rank = [];
    this.size = [];
    this.parent = [];
    this.nRedundantEdges = []

    for (var i = 0; i < N; ++i) {
        this.rank.push(0);
        this.size.push(1);
        this.parent.push(i);
        this.nRedundantEdges.push(0);
    }
}

DisjointSet.prototype.findSetRoot = function(a) {
    if (this.parent[a] === a) {
        return a;
    }

    return this.parent[a] = this.findSetRoot(this.parent[a]); // Compress the path to the root
};

DisjointSet.prototype.mergeSets = function(a, b) {
    a = this.findSetRoot(a);
    b = this.findSetRoot(b);

    if (a === b) {
        ++this.nRedundantEdges[a];
        return false;
    }

    if (this.rank[a] > this.rank[b]) {
        // Make a the root
        this.size[a] += this.size[b];
        this.nRedundantEdges[a] += this.nRedundantEdges[b];
        this.parent[b] = a;
    } else if (this.rank[b] > this.rank[b]) {
        // Make b the root
        this.size[b] += this.size[a];
        this.nRedundantEdges[b] += this.nRedundantEdges[a];
        this.parent[a] = b;
    } else {
        // Make a the root and increase its rank
        this.size[a] += this.size[b];
        this.nRedundantEdges[a] += this.nRedundantEdges[b];
        this.parent[b] = a;
        ++this.rank[a];
    }

    return true;
};

DisjointSet.prototype.processSets = function() {
    var sets = [];
    var seen = {};
    
    for (var i = 0; i < this.N; ++i) {
        var root = this.findSetRoot(i);
        
        if (!seen[root]) {
            seen[root] = true;
            sets.push({ size: this.size[root], nRedundantEdges: this.nRedundantEdges[root]})
        }
    }

    sets.sort(function(setA, setB) { return setB.size - setA.size; });

    return sets;
};

DisjointSet.prototype.getSetSize = function(a) {
    return this.size[this.findSetRoot(a)];
};

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

function main() {
    var t = parseInt(readLine());
    for(var a0 = 0; a0 < t; a0++){
        var n_temp = readLine().split(' ');
        var n = parseInt(n_temp[0]);
        var m = parseInt(n_temp[1]);
        
        var ds = new DisjointSet(n);
        var edges = [];
        
        for(var a1 = 0; a1 < m; a1++){
            var x_temp = readLine().split(' ');
            var x = parseInt(x_temp[0]) - 1;
            var y = parseInt(x_temp[1]) - 1;
            
            var edge = new Edge(x, y);
            
            if (!ds.mergeSets(x, y)) {
                edge.priority = -1;
            }
            
            edges.push(edge);
        }
        
        var sets = ds.processSets();
        var answer = 0;
        var numConnections = 0;
        var totalRedundant = 0;
        
        for (var i = 0; i < sets.length; ++i) {
            var set = sets[i];
            
            totalRedundant += set.nRedundantEdges;
            
            for (var j = 1; j < set.size; ++j) {
                answer += numConnections + j * (j + 1);
            }
            
            numConnections += (set.size - 1) * (set.size);
        }
        
        answer += totalRedundant * numConnections;
        
        console.log(answer);
    }
}

The Value of Friendship Python Solution

#!/bin/python3

import sys

class Node:
    def __init__(self, i):
        self.parent = self
        self.rank = 0
        self.index = i
        self.cluster_size = 0
        
    def union(self, y):
        xRoot = self.find()
        yRoot = y.find()
        if xRoot == yRoot:
            return
        
        if xRoot.rank < yRoot.rank:
            xRoot.parent = yRoot
        elif yRoot.rank < xRoot.rank:
            yRoot.parent = xRoot
        else:
            yRoot.parent = xRoot
            xRoot.rank += 1
            
    def find(self):
        if self.parent != self:
            self.parent = self.parent.find()
        return self.parent

def from_block(x):
    return (x * (x-1) * (x+1)) // 3
    
t = int(input().strip())
for a0 in range(t):
    n,m = input().strip().split(' ')
    n,m = [int(n),int(m)]
    
    nodes = [Node(i) for i in range(n)]
    
    for a1 in range(m):
        x,y = input().strip().split(' ')
        x,y = [int(x)-1,int(y)-1]
        
        
        # Disjoint sets!
        nodes[x].union(nodes[y])
        
    # Parents
    for i in range(n):
        nodes[i].find().cluster_size += 1
        
    # Check the set sizes
    sizes = list(reversed(sorted([x.cluster_size for x in nodes if x.cluster_size > 0])))
        
    # Here we can implement the whole algorithm:
  
    
    left_edges = m
    result = 0
    sizes_index = 0
    while m > 0 and sizes_index < len(sizes):
        current_size = sizes[sizes_index]
        sizes_index += 1
        
        if current_size <= m:
            result += from_block(current_size)
            result += (current_size * (current_size - 1) * (m - current_size + 1))
        else:
            result += from_block(m)
            
        m -= (current_size - 1)
        
    print(result)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python