HackerRank The Value of Friendship Solution Yashwant Parihar, May 19, 2023May 19, 2023 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 ʼn 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 FormatThe 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 CcppCSharpHackerrank Solutionsjavajavascriptpython