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 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
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}";
}
}
///aaaaaaaaaaaaaaaaaaaaaaaaaaaThe 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)
