Killjee and cities | Editorial by aksingh007

This problem is solved using DSU data-structure. Here, we initially do the union and then address the queries. Learn [here](https://www.hackerearth.com/practice/notes/disjoint-set-union-union-find/)
in details.

```
import java.util.*;
class Sets{
	int tot_nodes;
	int rank[];
	int parent[];
    int size[];          //RETURNS THE SIZE OF SET CONTAINING ith ELEMENT;
	Sets(int tot_nodes){
		rank=new int[tot_nodes+1];
		parent=new int[tot_nodes+1];
        size=new int[tot_nodes+1];
		this.tot_nodes=tot_nodes;
		for(int i=0;i<=tot_nodes;i++){
			parent[i]=i;
			rank[i]=0;
            size[i]=1;
		}
	}
	int find_set(int node){
		//System.out.println(":"+node+":");
		if(parent[node]!=node)
			parent[node]=find_set(parent[node]);
		return parent[node];
	}
	void union(int node1,int node2){
		int parent1=find_set(node1);
		int parent2=find_set(node2);
		//System.out.println(parent1+" "+parent2);
		if(parent1==parent2)
			return;
		if(rank[parent1]==rank[parent2]){
			parent[parent1]=parent2;
			rank[parent2]++;
            size[parent2]+=size[parent1];
		}
		else 
			if(rank[parent1]>rank[parent2]){
			parent[parent2]=parent1;
            size[parent1]+=size[parent2];
            }
		else{
			parent[parent2]=parent1;
             size[parent1]+=size[parent2];
        }
		return;
	}
	void print_sets(){
		for(int i=1;i<=tot_nodes;i++)
			System.out.print(find_set(i)+" ");
		return;
	}
    int count_set(int node){
        int p=find_set(node);
        return size[p];
    }
    int count(){
        int arr[]=new int[tot_nodes+1];
        for(int i=0;i<=tot_nodes;i++)
            arr[i]=find_set(i);
        Arrays.sort(arr);
        int c=0;
        for(int i=2;i<=tot_nodes;i++)
            if(arr[i]!=arr[i-1])
                c++;
        return c;
    }
}
class DJset{
	public static void main(String args[]){
		Scanner sc =new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		int temp=sc.nextInt();
		Sets set=new Sets(n);
		for(int i=0;i<m;i++){
			 
                int x1=sc.nextInt();  //FOR 'Q' FIND SIZE OF THE SET
                int y1=sc.nextInt();
                set.union(x1,y1);
            }
        int q=sc.nextInt();
        int temp2=sc.nextInt();
        int d=set.count();
        while(q-->0){
            int x=sc.nextInt();
            int y=sc.nextInt();
            if(set.find_set(x)==set.find_set(y))
                System.out.print(d+" ");
                else{
                    set.union(x,y);
                    d--;
                    System.out.print(d+" ");
                }
            
        }
          
			
	
	}
}
	
```

Killjee and cities | Editorial by aksingh007

Download submission

All caught up!

View submission

Is your resume even shortlisted?