In this HackerRank Friend Circle Queries Interview preparation kit problem You will be given q queries. After each query, you need to report the size of the largest friend circle (the largest group of friends) formed after considering that query.
Problem solution in Python programming.
#!/bin/python3
import math
import os
import random
import re
import sys
def init_cmp(mp,x,y):
if x not in mp:
mp[x]=x
if y not in mp:
mp[y]=y
def init_cc(cc,x,y):
if x not in cc:
cc[x]=1
if y not in cc:
cc[y]=1
def get_parent(mp,x):
while mp[x]!=x:
x=mp[x]
return x
# Complete the maxCircle function below.
def maxCircle(queries):
mp = {}
cc = {}
max_gp = 0
res = []
for q in queries:
init_cmp(mp,q[0],q[1])
init_cc(cc,q[0],q[1])
p1 = get_parent(mp,q[0])
p2 = get_parent(mp,q[1])
if p1!=p2:
if cc[p1]>cc[p2]:
mp[p2]=p1
cc[p1]=cc[p1]+cc[p2]
else:
mp[p1]=p2
cc[p2]=cc[p1]+cc[p2]
max_gp = max(max_gp,max(cc[p1],cc[p2]))
res.append(max_gp)
return res
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
q = int(input())
queries = []
for _ in range(q):
queries.append(list(map(int, input().rstrip().split())))
ans = maxCircle(queries)
fptr.write('n'.join(map(str, ans)))
fptr.write('n')
fptr.close()
Problem solution in Java Programming.
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
static class UnionFind {
Map<Integer, Integer> parents;
Map<Integer, Integer> sizes;
int max;
public UnionFind() {
parents = new HashMap<>();
sizes = new HashMap<>();
max = 0;
}
public void union(int v1, int v2) {
if (!parents.containsKey(v1)) {
parents.put(v1, v1);
sizes.put(v1, 1);
}
if (!parents.containsKey(v2)) {
parents.put(v2, v2);
sizes.put(v2, 1);
}
int p1 = find(v1), p2 = find(v2);
if (p1 == p2) return;
int s1 = sizes.get(p1), s2 = sizes.get(p2);
if (s1 < s2) {
parents.put(p1, p2);
sizes.put(p2, s1 + s2);
if (s1 + s2 > max) max = s1 + s2;
}else {
parents.put(p2, p1);
sizes.put(p1, s1 + s2);
if (s1 + s2 > max) max = s1 + s2;
}
}
public int find(int v) {
while (parents.get(v) != v) {
parents.put(v, parents.get(parents.get(v)));
v = parents.get(v);
}
return v;
}
}
// Complete the maxCircle function below.
static int[] maxCircle(int[][] queries) {
UnionFind uf = new UnionFind();
int[] res = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
uf.union(queries[i][0], queries[i][1]);
res[i] = uf.max;
}
return res;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int q = scanner.nextInt();
scanner.skip("(rn|[nru2028u2029u0085])?");
int[][] queries = new int[q][2];
for (int i = 0; i < q; i++) {
String[] queriesRowItems = scanner.nextLine().split(" ");
scanner.skip("(rn|[nru2028u2029u0085])?");
for (int j = 0; j < 2; j++) {
int queriesItem = Integer.parseInt(queriesRowItems[j]);
queries[i][j] = queriesItem;
}
}
int[] ans = maxCircle(queries);
for (int i = 0; i < ans.length; i++) {
bufferedWriter.write(String.valueOf(ans[i]));
if (i != ans.length - 1) {
bufferedWriter.write("n");
}
}
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
Problem solution in C++ programming.
#include<bits/stdc++.h> using namespace std; const int MAX=500005; int a[MAX], s[MAX]; set<int> sz; void init(int n) { for(int i=0;i<n;i++) { a[i]=i; s[i]=1; } } int root(int x) { while(a[x]!=x) { a[x]=a[a[x]]; x=a[x]; } return x; } void join(int x,int y) { int rx=root(x); int ry=root(y); if(rx==ry) return; if(s[rx]>s[ry]) { s[rx]+=s[ry]; a[ry]=rx; sz.insert(-s[rx]); } else { s[ry]+=s[rx]; a[rx]=ry; sz.insert(-s[ry]); } } int main() { int q; vector<pair<int,int> > queries; map<int,int> m; vector<int> aux; scanf("%d",&q); for(int i=0;i<q;i++) { int x,y; scanf("%d%d",&x,&y); queries.push_back(make_pair(x,y)); aux.push_back(x); aux.push_back(y); } sort(aux.begin(),aux.end()); int curr=1; for(int i=0;i<aux.size();i++) { if(i==0||aux[i]!=aux[i-1]) { m[aux[i]]=curr++; } } for(int i=0;i<q;i++) { queries[i].first=m[queries[i].first]; queries[i].second=m[queries[i].second]; } init(curr); for(int i=0;i<q;i++) { join(queries[i].first,queries[i].second); printf("%dn",-*(sz.begin())); } return 0; }