HackerRank Merging Communities problem solution

In this tutorial, we are going to solve or make a solution to the Merging Communities problem. so here we have n queries that representing the n communities. we need to print the size of the community to which person belongs.

Problem solution in Python programming.

#!/bin/python

import sys
from collections import deque

N, Q = map(int,input().strip().split(' '))

s = [i for i in range(N+1)]
cnt = [0]+[1 for i in range(N)]

for i in range(Q):
    inpt = input().strip().split(' ')
    qry = inpt[0]
    a = sorted(map(lambda x: int(x),inpt[1:]))
    i0 = a[0]
    if qry == 'M' and s[i0] != s[a[1]]:
        i1 = a[1]
        tmp = deque()
        while i0 != s[i0]:
            tmp.append(i0)
            i0 = s[i0]
        while i1 != s[i1]:
            tmp.append(i1)
            i1 = s[i1]
        if s[i0] != s[i1]:
            cnt[s[i0]] += cnt[s[i1]]
            tmp.append(i1)
            for ix in tmp:
                s[ix] = s[i0]
    elif qry == 'Q':
        tmp = deque()
        while i0 != s[i0]:
            tmp.append(i0)
            i0 = s[i0]
        for ix in tmp:
            s[ix] = s[i0]
        print(cnt[i0])

Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] line = scanner.nextLine().split(" ");
        int n = Integer.valueOf(line[0]);
        int q = Integer.valueOf(line[1]);

        int[] arr = new int[n+1];
        for(int i=0; i<=n; i++) {
            arr[i] = -1;
        }

        for(int i=0; i<q; i++) {
            line = scanner.nextLine().split(" ");
            
            if(line.length == 2) {
                int a = Integer.valueOf(line[1]);
                int root = getRoot(arr, a);
                System.out.println(size(arr, root));
            } else {
                int a = Integer.valueOf(line[1]);
                int b = Integer.valueOf(line[2]);
                
                int aroot = getRoot(arr, a);
                int broot = getRoot(arr, b);
                if(aroot == broot)
                    continue;
                
                if(size(arr, aroot) > size(arr, broot)) {
                    arr[aroot] += arr[broot];
                    arr[broot] = aroot;
                } else {
                    arr[broot] += arr[aroot];
                    arr[aroot] = broot;
                }
            }
        }
    }
    
    static int getRoot(int[] arr, int a) {
        int root = a;
        while(arr[root] > 0) {
            root = arr[root];
        }
        
        if(a != root)
            arr[a] = root;
        
        return root;
    }
    
    static int size(int[] arr, int a) {
        return -1 * arr[a];
    }
}

Problem solution in C++ programming.

#include<stdio.h>
#define mem(a,v) memset(a,v,sizeof(a))
long int parent[100005],rank[100005],val[100005];
long int find(long int x)
{
    if(parent[x]==x)
    return x;
    return find(parent[x]);
}
void _union(long int x,long int y)
{
    long int vv,dd=find(x);
    long int hh=find(y);
    if(dd!=hh)
    {
    if(rank[hh]>rank[dd])
    {
        parent[dd]=hh;
    val[hh]+=val[dd];
    }
    else if(rank[hh]<rank[dd])
    {
        parent[hh]=dd;
    val[dd]+=val[hh];
    }
    else
    {
    parent[hh]=dd;
    val[dd]+=val[hh];
    rank[dd]++;    
    }
    }
}
int main()
{
    long int c,d,t,i,e;
    char ff[3];

for(i=0;i<=100005;i++)
    {
        parent[i]=i;
        val[i]=1;
        rank[i]=1;
    }
    scanf("%ld%ld",&c,&d);
    for(i=0;i<=c;i++)
    parent[i]=i;
    while(d--)
    {
        scanf("%s",ff);
        if(ff[0]=='M')
        {
        scanf("%ld%ld",&e,&t);
        _union(e,t);
        }
        else
        {
            scanf("%ld",&e);
        printf("%ldn",val[find(e)]);
        }
    }
    return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

typedef struct Node{
    int cnt;
    int par;
}node;

node *com_array;

int find_parent(int n){
    while(com_array[n].par != -1){
        n=com_array[n].par;
    }
    return n;
}

void mergeCom(int p1, int p2){
    int max,low,par1,par2;
    if(p1==p2) return;
    par1=find_parent(p1);
    par2=find_parent(p2);

    if((par1>=0) &&  ( par1 == par2)) return;
    
    if(com_array[par1].cnt>=com_array[par2].cnt){
        max=par1;
        low=par2;
    }
    else{
        max=par2;
        low=par1;
    }
    com_array[max].cnt+=com_array[low].cnt;
    com_array[low].par=max;
}

int main() {
    int q,*res,n;
    char o;
    int i,p1,p2,qcnt=0;
    scanf("%d %d",&n,&q);
    com_array=(node*)malloc(n*sizeof(node));
    for(i=0;i<n;i++){
        com_array[i].par=-1;
        com_array[i].cnt=1;
    }
    res=(int*)calloc(q,sizeof(int));
    for(i=0;i<q;i++){
        scanf(" %c",&o);
        if(o=='Q'){
            int par;
            scanf("%d",&p1);
            par=find_parent(p1-1);
            res[qcnt++]=com_array[par].cnt;
        }
        else{
            scanf("%d %d",&p1,&p2);   
            mergeCom(p1-1,p2-1);
        }
    }
    for(i=0;i<qcnt;i++) printf("%dn",res[i]);
    return 0;
}

Problem solution in JavaScript programming.

function processData(input) {
    //Enter your code here
    var arr = input.split("n");
    var [n, queries] = arr[0].split(" ");
    var uf = new UF();
    for (var i = 1; i <= n; i++) {
        uf.add(i);
    }
    var result = "";
    for (var i = 1; i < arr.length; i++) {
        var list = arr[i].split(" ");
        if (list[0] === "Q") {
            // result.push(uf.count[uf.find(list[1])]);
            if (result !== "") {
                result += "n";
            }
            result += uf.count[uf.find(list[1])];
        } else {
            uf.union(list[1], list[2]);
        }
    }
    console.log(result);
} 

function UF() {
    this.parent = [];
    this.count = [];
}

UF.prototype.add = function(i) {
    this.parent[i] = i;
    this.count[i] = 1;
}

UF.prototype.find = function(i) {
    var j = i;
    while (this.parent[i] !== i) {
        i = this.parent[i];
    }
    while (j !== i) {
        var pj = this.parent[j];
        this.parent[j] = i;
        j = pj;
    }
    return i;
}

UF.prototype.union = function (i, j) {
    var pi = this.find(i);
    var pj = this.find(j);
    if (pi !== pj) {
        this.parent[pj] = pi;
        this.count[pi] += this.count[pj]; 
    }
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});