CAG - Editorial

Problem Link :–

Contest

Practice

Author :-- Ranjan Kumar

Editorialist :-- Ranjan Kumar

Difficulty

Medium.

Pre-Requisites :–

Graph,dfs

Problem Statement :–

There are N students among whom some gifts are to be distributed by the college. There are M pairs of friends (A,B) in them such that Student A will only accept a gift if Student B is given a gift too but not vice versa. The college wants to distribute the minimum possible number of gifts. Each gift costs K rupees. You have to find the minimum amount of money the college needs to spend.

Quick Explanation :–

Let us define a Directed Graph whose vertices are students. A directed edge connecting Student A to Student B would mean that Student B is a friend of Student A i.e. Student A will accept a gift only if Student B is given a gift too.

Therefore, by induction, a connected component on this graph will mean that either all of the connected students (vertices) would get a gift or none would. Since the college wants to give the minimum possible number of gifts (but not zero), we have to find the component with the minimum number of vertices. Our answer will be K times the size of this minimum component.

Detailed Approach :–

Let us store the graph using adjacency list representation. The connected components can be easily found using Depth-First Search.

Let us consider we start dfs from a source vertex S.

First we initialize all vertices as unvisited. Then, by using a counter with the dfs, we can find the number of vertices connected to S (i.e. The number of students who will have to be given a gift if S receives one). Then we will again set all vertices as unvisited and then find dfs from the next vertex. This process will be continued till we reach at the last vertex. Then we will find the connected component with minimum number of vertices and k times that number of elements will be our final answer.

Our approach here is-

-> Initialize a variable that will store the size of the smallest component (say min_size) with infinity.

**->**Repeat for i=1 to n

• Initialize all the vertices as unvisited.

• Do a dfs using the i’th vertex as source and find the number of vertices connected with it. (Let’s call it component_size). This counter also includes the source vertex itself.

• If component_size is less than min_size, update min_size with the value component_size.

-> Output the answer as K times min_size.

Time Complexity :–

O(N^2)

Solution :–

Setter’s Solution can be found here.

Feel free to post comments if anything is not clear to you.

1 Like

Cant we use concept of SCC here