Table of Contents
The Value of Friendship – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ The Value of Friendship HackerRank Solution
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 200005;
int f[N] , s[N];
int getf(int x) {
return x == f[x] ? x : f[x] = getf(f[x]);
}
int main(){
int t;
cin >> t;
for(int a0 = 0; a0 < t; a0++){
int n;
int m;
cin >> n >> m;
long long res = 0 , sum = n;
for (int i = 1 ; i <= n ; ++ i) {
f[i] = i;
s[i] = 1;
}
for(int a1 = 0; a1 < m; a1++){
int x;
int y;
cin >> x >> y;
x = getf(x) , y = getf(y);
if (x != y) {
f[x] = y;
sum += (long long)2 * s[y] * s[x];
s[y] += s[x];
}
}
vector<int> V;
for (int i = 1 ; i <= n ; ++ i) {
if (getf(i) == i) {
V.push_back(s[i]);
}
}
sort(V.begin() , V.end());
reverse(V.begin() , V.end());
int now = m;
long long w = n;
for (int i = 0 ; i < V.size() ; ++ i) {
int x = V[i];
for (int k = 1 ; k < x ; ++ k) {
w += 2 * k;
-- now;
res += w;
}
}
res += sum * now;
res -= (long long)m * n;
cout << res << endl;
}
return 0;
}
Java The Value of Friendship HackerRank Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int z = 0; z < t; z++) {
int n = sc.nextInt();
int m = sc.nextInt();
ArrayList<ArrayList<Integer>> neigh = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < n; i++)
neigh.add(new ArrayList<Integer>());
for (int i = 0; i < m; i++) {
int u = sc.nextInt()-1;
int v = sc.nextInt()-1;
neigh.get(u).add(v);
neigh.get(v).add(u);
}
long[] adds = new long[n+1];
for (int i = 2; i <= n; i++) {
adds[i] = adds[i-1] + ((long)i)*(i-1);
}
ArrayList<Integer> cycles = new ArrayList<Integer>();
boolean[] vis = new boolean[n];
for (int i = 0; i < n; i++) {
if (!vis[i]) {
int clen = 1;
vis[i] = true;
ArrayDeque<Integer> qu = new ArrayDeque<Integer>();
qu.add(i);
while (!qu.isEmpty()) {
int u = qu.removeFirst();
for (int v : neigh.get(u)) {
if (!vis[v]) {
clen++;
qu.add(v);
vis[v] = true;
}
}
}
cycles.add(clen);
}
}
long ans = 0;
Collections.sort(cycles);
int index = 0;
for (int i = cycles.size()-1; i >= 0; i--) {
int c = cycles.get(i);
ans += adds[c];
index += c-1;
ans += ((long)c)*(c-1)*(m-index);
}
System.out.println(ans);
}
}
}
Python 3 The Value of Friendship HackerRank Solution
def grow(n):
res = 0
for i in range(1, n):
res += i*(i+1)
#print("-->", i, res)
return res
def mark(x):
z = x
while z: z = z[0]
if x is not z: x[0] = z
return z
def mark2(x):
z = x
while z and type(z) == list: z = z[0]
if x is not z: x[0] = z
return z
T = int(input())
for t in range(T):
n, m = map(int, input().split())
work = [[] for i in range(n)]
lost = 0
for i in range(m):
u, v = map(int, input().split())
u -= 1
v -= 1
mu = mark(work[u])
mv = mark(work[v])
if mu is not mv:
mu.append(mv)
else:
lost += 1
no = 1
dic = {}
for i in range(n):
z = mark2(work[i])
if not z:
z.append(no)
z = no
no += 1
dic[z] = 1
else:
dic[z] += 1
res = 0
cur = 0
for v in sorted(dic.values(), reverse = True):
res += grow(v) + (v-1) * cur
cur += v*(v-1)
#print(v, cur, res)
res += lost * cur
print(res)
Python 2 The Value of Friendship HackerRank Solution
def root(x):
if par[x]==-1:
return x
par[x] = root(par[x])
return par[x]
def unite(x,y):
x = root(x)
y = root(y)
if x == y :
return
if x < y:
x,y = y,x
sz[x] += sz[y]
par[y] = x
for t in xrange(input()):
n,m = map( int, raw_input().split() )
par = [-1]*(n+1)
sz = [1]*(n+1)
for i in xrange(m):
xx,yy = map( int, raw_input().split() )
unite( xx, yy )
ar = []
vis = [0]*(n+1)
for i in xrange(1,n+1):
x = root(i)
if vis[x] == 0 :
vis[x] = 1
ar.append(sz[x])
ar = sorted(ar)[::-1]
ans = 0
for v in ar :
ans += ( v*v*v - v )/3
m -= v
m += 1
ans += m*v*(v-1)
print ans
C The Value of Friendship HackerRank Solution
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <string.h>
#include <stdlib.h>
int n, m;
int graph[500002][2]; // [0]-neighbor node, [1]-next
int gend;
int nodeedge[100001];
int used[100001];
int bfs(int v, int *edgen) {
int q[100001];
int i, j, qe=1;
q[0]=v;
used[v]=1;
*edgen=nodeedge[v];
for (i=0; i<qe; i++) {
for (j=q[i]; j && (v=graph[j][0]); j=graph[j][1]) {
if (!used[v]) {
q[qe++]=v;
used[v]=1;
*edgen+=nodeedge[v];
}
}
}
return qe;
}
static int cmp(const void *p1, const void *p2) {
return *((const int *)p2)-*((const int *)p1);
}
uint64_t solve(void) {
uint64_t total=0, tt=0, t;
int noden[100001], edgen, rededgen=0;
int i, nni=0;
for (i=1; i<=n; i++) {
if (used[i])
continue;
noden[nni]=bfs(i, &edgen);
if (edgen)
rededgen+=edgen-noden[nni++]+1;
}
qsort(noden, nni, sizeof(int), cmp);
for (i=0; i<nni; i++) {
t=noden[i];
total+=(t*(t+1)*(t-1))/3+(t-1)*tt;
tt+=t*(t-1);
}
total+=tt*rededgen;
return total;
}
int main(void) {
int i, q, u, v;
scanf("%d\n", &q);
while (q--) {
scanf("%d%d\n", &n, &m);
gend=n+1;
for (i=0; i<m; i++) {
scanf("%d%d\n", &u, &v);
if (graph[u][0]) {
graph[gend][0]=graph[u][0];
graph[gend][1]=graph[u][1];
graph[u][0]=v;
graph[u][1]=gend++;
} else {
graph[u][0]=v;
}
if (graph[v][0]) {
graph[gend][0]=graph[v][0];
graph[gend][1]=graph[v][1];
graph[v][0]=u;
graph[v][1]=gend++;
} else {
graph[v][0]=u;
}
nodeedge[u]++;
}
printf("%"PRIu64"\n", solve());
memset(graph, 0, sizeof(graph));
memset(nodeedge, 0, sizeof(nodeedge));
memset(used, 0, sizeof(used));
gend=0;
}
return 0;
}
Leave a comment below
