Merging Communities| Disjoint Set
TASK(hard)
People connect with each other in a social network. A connection between Person i and Person j is represented as Mij. 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 people representing n communities. Suppose person 1 and 2 connected and later 2 and 2 connected, then 1,2, and 3 will belong to the same community.
There are two types of queries:
- communities containing persons i and j are merged if they belong to different communities.
- 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<=105
1<=q<=2*105
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
SOLUTION 1
# Enter your code here. Read input from STDIN. Print output to STDOUT
N, Q = tuple(map(int, input().split(' ')))
dict_one = dict()
dict_two = dict()
for i in range(N):
dict_one[i] = str(i)
dict_two[str(i)] = [i]
for q in range(Q):
command = input().split(' ')
if command[0] == 'Q':
I = int(command[1]) - 1
community = dict_one[I]
print(len(dict_two[community]))
else:
#command[0] == M, M I J
I, J = int(command[1]) - 1, int(command[2]) - 1
com1, com2 = dict_one[I], dict_one[J]
if com1 != com2:
x, y = dict_two[com1], dict_two[com2]
if len(x) > len(y):
x, y = y, x
com1, com2 = com2, com1
for k in x:
dict_one[k] = com2
y.extend(x)
del dict_two[com1]
EXPLANATION STEPS
- Initialize Data Structures: Create a size array to track the size of each community, initially set to 1 for each member.
- Define Union-Find Functions: Find: Implement path compression to efficiently find the representative of a community. Union: Merge two communities using size optimization, ensuring the smaller community is merged into the larger one.
- Process Union Operations: For each merge operation, use the union function to combine the specified communities.
- Process Queries: For each query, use the find function to determine the size of the community to which the queried member belongs.
- Output Results: Print the size of the community for each query.
