HackerRank Friend Circle Queries problem solution

In this HackerRank Friend Circle Queries problem solution, 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.

Function Description

Complete the function maxCircle in the editor below. It must return an array of integers representing the size of the maximum circle of friends after each query.

maxCircle has the following parameter(s):

• queries: an array of integer arrays, each with two elements indicating a new friendship

HackerRank Friend Circle Queries problem solution in Python.

#!/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()

Friend Circle Queries problem solution in Java.

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;
}