Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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:
- M i j => communities containing persons i and j are merged if they belong to different communities.
- 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;
}
#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;
}
#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];
}
}
#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);
});
#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])