Maximum component

3.1

11 votes
Fenwick Tree, Graphs, Depth First Search, Disjoint Set Union, Algorithms
Problem

You are given a graph consisting of N nodes. Initially, there is no edge in the graph. You have to process Q queries of the following two types:

  • 1 X Y: connect nodes X and Y with an undirected edge.
  • 2 K: Print the size of the largest connected component if K extra undirected edges are added between any pair of nodes of the graph.

Note that the edges connected in the type 2 query are not considered in further queries.

Note: Since the size of input-output is large, prefer using fast input-output methods.

Input format

  • The first line of input contains denoting the number of nodes and Q denoting the number of queries respectively.
  • Q lines follow. Each of these lines contains an integer type[i], denoting the type of the i-th query. if type[i] is 1, it contains two more integers X, Y,  if type[i] = 2, it contains an integer K.

Output format
For each query of type 2, print the size of the largest connected component in a separate line.

Constraints

2N,Q41051xi<yiN1typei21KN

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Query 1: Add an edge between nodes 1 and 2 and another edge between nodes 1 and 3. Now the nodes 1, 2 and 3 form the largest component.

Query 2: Nodes 2 and 3 are connected with an edge.

Query 3:  Add an edge between nodes 2 and 4. Now the nodes 2, 3 and 4 form the largest component.

Query 4: Nodes 1 and 5 are connected with an edge.

Query 5: Nodes 1 and 2 are connected with an edge.

Query 6:  Add an edge between nodes 4 and 5. Now the nodes 12, 3, 4 and 5 form the largest component.

Editor Image

?