The Social Network

Problem Statement

A student in a college is planning to start a new social networking website for his college community. In this social network, initially, all people belong to different communities. Then, if X connects with Y, the result is the merger of the communities to which X and Y belong to. Suppose, person X and Y connected and later Y and Z connected, then X,Y and Z will belong to the same community.

Input Format

The first line will contain 2 integers U and V, separated by single space denoting number of persons and number of queries respectively. The next U lines will denote each person's details with each detail separated by a single space. The details are : "id of the person" "name of the person" "age of the person". The next V lines will contain V queries. There are 4 types of queries for this problem:-

1. M id1 id2 : This query will merge the 2 communities to which person with id1 and id2 belong to. If both of them belong to same community, then no need to merge.
2. F id1 id2 : This query will find whether person with id1 and person with id2 belong to the same community or not. Your answer has to be “YES” or “NO”.
3. W id1 : This query will return the number of persons in a community to which a person with id1 belongs to.
4. P id1 : This query will print the details of the person with id1.

Output Format

The output of the queries.

Sample Input

6 12
1 Harish 25
2 Anurag 24
3 Gaurav 25
4 Shaifali 22
5 Ranjana 23
6 Krishana 29
F 3 6
M 1 2
M 4 6
W 4
P 4
M 3 5
M 5 4
M 3 6
F 1 6
M 1 6
F 1 6
W 5

Sample Output

NO
2
4 Shaifali 22
NO
YES
6

Solution

	import java.util.*;
	import java.util.concurrent.LinkedBlockingDeque;
	class Person {
	private int id;
	private String name;
	private int age;
	private int parent;
	Person(Scanner input){
	this.id = input.nextInt();
	this.name = input.next();
	this.age = input.nextInt();
	this.parent = this.id;
	}
	public int getParent() {
	return parent;
	}
	public void setParent(int parent) {
	this.parent = parent;
	}
	public int getId() {
	return id;
	}
	public void setId(int id) {
	this.id = id;
	}
	public String getName() {
	return name;
	}
	public void setName(String name) {
	this.name = name;
	}
	public int getAge() {
	return age;
	}
	public void setAge(int age) {
	this.age = age;
	}
	}
	public class Solution {
	public static TreeMap<Integer, Person> trMapPerson
	= new TreeMap<Integer, Person>();
	public static TreeMap<Integer, LinkedList<Person>> trMapSet =
	new TreeMap<Integer, LinkedList<Person>>();
	enum option {M, F, W, P};
	public static void main(String[] args){
	Scanner input = new Scanner(System.in);
	int u = input.nextInt();
	int v = input.nextInt();
	for(int i = 1; i <= u ; i ++){
	trMapPerson.put(i, new Person(input));
	trMapSet.put(i, new LinkedList<Person>());
	trMapSet.get(i).add(trMapPerson.get(i));
	}
	// System.out.println(trMapPerson.toString());
	// System.out.println(trMapSet.toString());
	while(v != 0){
	performQuery(input);
	v--;
	}
	}
	public static void performQuery(Scanner input){
	option userOption;
	userOption = option.valueOf(input.next());
	switch(userOption){
	case M : merge(input);
	break;
	case F : find(input);
	break;
	case W : length(input);
	break;
	case P : printDetail(input);
	break;
	}
	}
	public static void length(Scanner input){
	int id = input.nextInt();
	int community = trMapPerson.get(id).getParent();
	System.out.println(trMapSet.get(community).size());
	}
	public static void merge(Scanner input){
	int id1 = input.nextInt();
	int id2 = input.nextInt();
	if(trMapPerson.get(id1).getParent()!=
	trMapPerson.get(id2).getParent())
	{
	if(trMapSet.get(trMapPerson.get(id1).getParent()).size()
	<= trMapSet.get(trMapPerson.get(id2).getParent()).size()){
	for(Person j : trMapSet.get(trMapPerson.get(id2).getParent())){
	trMapSet.get(trMapPerson.get(id1).getParent()).add(j);
	j.setParent(trMapPerson.get(id1).getParent());
	}
	} else
	{
	for(Person j : trMapSet.get(trMapPerson.get(id1).getParent())){
	trMapSet.get(trMapPerson.get(id2).getParent()).add(j);
	j.setParent(trMapPerson.get(id2).getParent());
	}
	}
	}
	if(trMapPerson.get(id1).getParent()!=trMapPerson.get(id2).getParent())
	{
	if(trMapSet.keySet().contains(id2)){
	trMapSet.remove(id2);
	}
	}
	}
	public static void printDetail(Scanner input){
	int id = input.nextInt();
	System.out.print(id);
	System.out.print(" " + trMapPerson.get(id).getName());
	System.out.println(" " + trMapPerson.get(id).getAge());
	}
	public static void find(Scanner input){
	int id1 = input.nextInt();
	int id2 = input.nextInt();
	if(trMapPerson.get(id1).getParent() ==
	trMapPerson.get(id2).getParent()){
	System.out.println("YES");
	}
	else System.out.println("NO");
	}
	}

view raw socialNetwork.java hosted with ❤ by GitHub