Algorithm


Problem Name: Data Structures - Merging Communities

Problem Link: https://www.hackerrank.com/challenges/array-and-simple-queries/problem?isFullScreen=true

In this HackerRank in Data Structures - Array and simple queries solutions

People connect with each other in a social network. A connection between Person i and Person j is represented as M i j. When two persons belonging to different communities connect, the net effect is the merge the communities which i and j belong to.

At the beginning, there are n At the beginning, there are n communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then 1, 2 and 3 will belong to the same community.

There are two types of queries:

  1. M i j => communities containing persons i and j are merged if they belong to different communities.
  2. Q i => print the size of the community to which person i belongs.

Input Format

The first line of input contains 2 space-separated integers n and q the number of people and the number of queries.
The next q lines will contain the queries.

Constraints

1 <= n <= 10**5

1 <= q <= 2 * 10**5

Output Format

The output of the queries.

Sample Input

STDIN Function ----- -------- 3 6 n = 3, q = 6 Q 1 print the size of the community containing person 1 M 1 2 merge the communities containing persons 1 and 2 ... Q 2 M 2 3 Q 3 Q 2

Sample Output

1
2
3
3

Explanation

Initial size of each of the community is 1.

 

 

 

 

Code Examples

#1 Code Example with C Programming

Code - 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("%d\n",res[i]>;
    return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - 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("%ld\n",val[find(e)]>;
        }
    }
    return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - 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];
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Javascript Programming

Code - 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);
});
Copy The Code & Try With Live Editor

#5 Code Example with Python Programming

Code - Python Programming


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])
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Eye and Identity in PYTHON solution in Hackerrank
Next
[Solved] Floor, Ceil and Rint in PYTHON solution in Hackerrank