# HackerRank Friend Circle Queries problem solution

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("(\r\n|[\n\r\u2028\u2029\u0085])?");

int[][] queries = new int[q][2];

for (int i = 0; i < q; i++) {
String[] queriesRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

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("%d\n",-*(sz.begin()));
}
return 0;
}```