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:
communities containing person I and J merged (if they belong to different communities).
print the size of the community to which person I belong.
Example:
Input:
3 6Q 1M 1 2Q 2M 2 3Q 3Q 2
Output:
1233
Approach
C++
#include <bits/stdc++.h>using namespace std;int parent[1000001];int size1[1000001];void make_set(int n){for (int i = 1; i <= n; i++){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 a, int b){a = find(a);b = find(b);if (a != b){if (size1[a] < size1[b])swap(a, b);parent[b] = a;size1[a] += size1[b];}}int main(){int n, q;cin >> n >> q;make_set(n);while (q--){char c;int i, j;cin >> c >> i;if (c == 'Q'){int x = find(parent[i]);cout << size1[x] << "\n";}else{cin >> j;merge_set(i, j);}}return 0;}
No comments:
Post a Comment