We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
par and sz arrays are used to represent the parent and size of each node in the DSU.
The init function initializes the DSU, setting each node as its own parent and initializing the size of each component to 1.
The findParent function recursively finds the parent of a node and performs path compression to optimize future queries.
The Union function merges two components by updating the parent and size information.
In the main function, the code reads the number of people n and the number of queries q. It then initializes the DSU.
The loop processes each query. If the query is of type 'Q', it reads an index and prints the size of the component containing that index. If the query is of type 'U', it reads two indices and performs a union operation.
The time complexity of this solution is O(q * α(n)), where α is the inverse Ackermann function. The inverse Ackermann function is very slow-growing and practically constant, making the DSU operations almost linear in practice.
Note: The getchar() before reading the query type is used to consume the newline character left in the input buffer from the previous input operation. This ensures correct parsing of the subsequent input.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Merging Communities
You are viewing a single comment's thread. Return to all comments →
Here's a breakdown of the code:
par and sz arrays are used to represent the parent and size of each node in the DSU.
The init function initializes the DSU, setting each node as its own parent and initializing the size of each component to 1.
The findParent function recursively finds the parent of a node and performs path compression to optimize future queries.
The Union function merges two components by updating the parent and size information.
In the main function, the code reads the number of people n and the number of queries q. It then initializes the DSU.
The loop processes each query. If the query is of type 'Q', it reads an index and prints the size of the component containing that index. If the query is of type 'U', it reads two indices and performs a union operation.
The time complexity of this solution is O(q * α(n)), where α is the inverse Ackermann function. The inverse Ackermann function is very slow-growing and practically constant, making the DSU operations almost linear in practice.
Note: The getchar() before reading the query type is used to consume the newline character left in the input buffer from the previous input operation. This ensures correct parsing of the subsequent input.