Merging Communities

                            Solution in C :

In C ++ :




#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int f[100005], s[100005];
int find(int x) {
    if (x == f[x]) return x;
    return f[x] = find(f[x]);
}
void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    if (s[fx] > s[fy]) {
        f[fy] = fx;
        s[fx] += s[fy];
    } else {
        f[fx] = fy;
        s[fy] += s[fx];
    }
}
int Q, N;
char c[5];
int main() {
    scanf("%d%d", &N, &Q);
    for (int i = 1; i <= N; ++i) f[i] = i, s[i] = 1;
    for (int i = 0; i < Q; ++i) {
        scanf("%s", c);
        if (c[0] == 'M') {
            int x, y; scanf("%d%d", &x, &y);
            merge(x, y);
        } else {
            int x; scanf("%d", &x);
            printf("%d\n", s[find(x)]);
        }
    }
    return 0;
}







In Java :





import java.util.Arrays;
import java.util.Scanner;

public class MergingCommunities {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int q = sc.nextInt();

		parent = new int[n];
		for (int i = 0; i < n; i++)
			parent[i] = i;

		size = new int[n];
		Arrays.fill(size, 1);

		while (q-- != 0) {
			// System.out.println(Arrays.toString(parent));
			// System.out.println(Arrays.toString(size));
			// System.out.println();
			String type = sc.next();
			if (type.equals("Q"))
				System.out.println(size[findSet(sc.nextInt() - 1)]);
			else
				union(sc.nextInt() - 1, sc.nextInt() - 1);
		}

	}

	static int[] parent;
	static int[] size;

	static int findSet(int x) {
		return parent[x] == x ? x : (parent[x] = findSet(parent[x]));
	}

	static void union(int x, int y) {
		if (findSet(x) != findSet(y))
			size[findSet(x)] = size[findSet(y)] = size[findSet(x)]
					+ size[findSet(y)];
		parent[findSet(x)] = findSet(y);
	}
}







In  C :




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








In Python3 :





[N,Q]=[int(x) for x in input().split()]
ds = [[i,1] for i in range(0,N+1)]
for q in range(Q):
    inp = input().split()
    if inp[0] == 'M':
        ind1 = int(inp[1])
        ind2 = int(inp[2])
        ind3 = ind2
        while ds[ind1][0] != ind1:
            ind1 = ds[ind1][0]
        while ds[ind2][0] != ind2:
            ind2 = ds[ind2][0]
        if ind1 == ind2:
            continue
        while ind3 != ind2:
            ind4 = ds[ind3][0]
            ds[ind3][0] = ind1
            ind3 = ind4
        ds[ind2][0] = ind1
        ds[ind1][1] += ds[ind2][1]
    else:
        ind1 = int(inp[1])
        while ds[ind1][0] != ind1:
            ind1 = ds[ind1][0]
        print(ds[ind1][1])