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("%ld\n",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("%d\n",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);
});
0 Comments