K3005 - Editorial

editorial
1

PROBLEM LINK:

(CodeChef: Practical coding for everyone)

Author: Rahul Verma
Tester: Rahul Verma
Editorialist: Rahul Verma

DIFFICULTY:

EASY-MEDIUM, MEDIUM

PREREQUISITES:

BFS or DFS or DSU or Graph Colouring

PROBLEM:

Piecity will be one of the first cities to have this clinical trial. The vaccine works in a very effective way which makes it cost effective too. It passes itself from one person to another itself just like the virus. ( very intuitive…!! )

Chef knows that there are n people in Piecity. Some of them are friends of each other. So the government decides to give it to certain individuals who will then spread it to other people who are their friends. i-th person wants ri rupees in exchange for taking the vaccine. When a person gets the vaccine he passes it on to all his friends, and they start spreading the vaccine to their friends (for free), and so on.

The vaccination of Piecity is finished when all n people have been vaccinated either directly or through their friends. What is the minimum amount of rupees government needs to spend in order to vaccinate the city ?

QUICK EXPLANATION:

you are given an undirected graph with weighted vertices.
You just have to take the sum of the minimum of all connected components of the graph.
This could be done using BFS or DFS several times or using a Disjoint union set .

EXPLANATION:

you are given an undirected graph with weighted vertices.
You just have to take the sum of the minimum of all connected components of the graph.
This could be done using BFS or DFS several times or using a Disjoint union set .

Untitled presentation (1)
Untitled presentation (1)960×540 53.1 KB

SOLUTIONS:

Solution

Java implementation for Disjoint union set is given below

Time complexity of DSU implementation = O(n*m)

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

public static void main(String[] args) throws Exception {
FastReader sc = new FastReader();

   int n=sc.nextInt();
   int m=sc.nextInt();
   long arr[]=new long[n];
    for (int i = 0; i <n ; i++) {
        arr[i]=sc.nextLong();
    }
   DSU d=new DSU(n);
    for (int i = 0; i <m ; i++) {
        int a=sc.nextInt()-1;
        int b=sc.nextInt()-1;
        d.unite(a,b);
    }
   HashMap<Integer,Long>hm=new HashMap<>();
    for (int i = 0; i < n ; i++) {
       int p=d.find(i);
       if(hm.containsKey(p))
           hm.put(p,Math.min(hm.get(p), arr[i]));
       else
           hm.put(p,arr[i]);
    }
    long sum=0;
    for(Integer k:hm.keySet())
        sum+=hm.get(k);
         System.out.println(sum);
}

}

class DSU
{
int parent[];
int rank[];
DSU(int n)
{
this.parent=new int[n];
this.rank=new int[n];
Arrays.fill(parent,-1);
Arrays.fill(rank,1);
}

int find(int s1)
{
    if(parent[s1]==-1)
        return s1;
    return parent[s1]=find(parent[s1]);
}

void unite(int s1,int s2)
{
    int p1=this.find(s1);
    int p2=this.find(s2);
    if(p1==p2)
        return;
    if(rank[p1]>rank[p2])
    {
        parent[p2]=p1;
        rank[p1]+=rank[p2];
    }
    else
    {
        parent[p1]=p2;
        rank[p2]+=rank[p1];
    }
}

}

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

If you want to learn more about Disjoint UnionSet click DSU video

This problem can also be solved using BFS or DFS .