Merging Communities

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 merger of both communities to which I and J belong to.

In the beginning, there are N people representing N communities.

There are two types of queries:

  1.  communities containing person I and J merged (if they belong to different communities).

  2.  print the size of the community to which person I belong.


Example:

Input:

3 6
Q 1
M 1 2
Q 2
M 2 3
Q 3
Q 2

Output:

1
2
3
3

Approach

C++

#include <bits/stdc++.h>
using namespace std;
int parent[1000001];
int size1[1000001];
void make_set(int n)
{
    for (int i = 1i <= ni++)
    {
        parent[i] = i;
        size1[i] = 1;
    }
}
int find(int v)
{
    if (v == parent[v])
        return v;
    return parent[v] = find(parent[v]);
}
void merge_set(int aint b)
{
    a = find(a);
    b = find(b);
    if (a != b)
    {
        if (size1[a] < size1[b])
            swap(ab);
        parent[b] = a;
        size1[a] += size1[b];
    }
}

int main()
{
    int nq;
    cin >> n >> q;
    make_set(n);
    while (q--)
    {
        char c;
        int ij;
        cin >> c >> i;
        if (c == 'Q')
        {
            int x = find(parent[i]);
            cout << size1[x<< "\n";
        }
        else
        {
            cin >> j;
            merge_set(ij);
        }
    }
    return 0;
}


No comments:

Post a Comment