Minimize number of notes required to be distributed among students
Given an array arr[] consisting of N strings representing the name of the students in the class and another array of pairs P[][2] such that P[i][0] likes P[i][1], the task is to find the minimum number of notes to be distributed in the class such that sharing of notes can take place only if a student likes another student either directly or indirectly.
Examples:
Input: arr[] = {Beginner, for, code, run, compile}, P[][] = {{Beginner, for}, {for, code}, {code, run}, {run, compile}, {run, for}}
Output: 3
Explanation:
Below is the image to represent the relationship among the students:From the above image:
- Students named {“for”, “code”, “run”} require a single copy of notes, since there exists a mutual relationship between them.
- Student named {“Beginner”} requires a single copy of notes.
- Student named {“compile”} also require a single copy of notes.
So, the minimum number of notes required is 3.
Input: arr[] = {Beginner, for, all, run, debug, compile}, P[][] = {{Beginner, for}, {for, all}, {all, Beginner}, {for, run}, {run, compile}, {compile, debug}, {debug, run}}
Output: 2
Approach: The given problem can be solved by finding the number of strongly connected components in a directed graph after generating the relationship graph with the given conditions. Follow the steps below to solve the problem:
- Create a hashmap, say M to map the names of the students to their respective index values.
- Traverse the array A using the variable i and map each string A[i] in the map M to value i.
- Iterate all the pairs in the array P and for each pair get the corresponding values from the HashMap, M and create a directed edge between them.
- After traversing all the pairs, a directed graph is formed having N vertices and M number of edges.
- Create an empty stack S, and perform the DFS traversal of the graph:
- Create a recursive function that takes the index of a node and a visited array.
- Mark the current node as visited and traverse all the adjacent and unmarked nodes and call the recursive function with the index of the adjacent node.
- After traversing all the neighbors of the current node, push the current node in the stack S.
- Reverse directions of all edges to obtain the transpose of the constructed graph.
- Iterate until the stack S is not empty and perform the following steps:
- Store the top element of the stack S in a variable V and pop it from the stack S.
- Perform the DFS traversal from node V as the source.
- Update the number of connected components and store the count in a variable, sat cnt.
- After completing the above steps, print the value of cnt as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Structure of class Graph class Graph { // No. of vertices int V; // An array of adjacency lists list< int >* adj; // Function that fills the stack // with the vertices v void fillOrder( int v, bool visited[], stack< int >& Stack); // Recursive function to perform // the DFS starting from v void DFSUtil( int v, bool visited[]); public : Graph( int V); void addEdge( int v, int w); // Function to count the number of // strongly connected components void countSCCs(); // Function that returns reverse // (or transpose) of the graph Graph getTranspose(); }; // Constructor of the Graph Graph::Graph( int V) { this ->V = V; adj = new list< int >[V]; } // Recursive function to perform the // DFS starting from v void Graph::DFSUtil( int v, bool visited[]) { // Mark the current node as visited visited[v] = true ; // Recur for all the vertices // adjacent to this vertex list< int >::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) { if (!visited[*i]) DFSUtil(*i, visited); } } // Function to return the reverse // (or transpose) of the graph Graph Graph::getTranspose() { Graph g(V); for ( int v = 0; v < V; v++) { // Recur for all the vertices // adjacent to this vertex list< int >::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) { g.adj[*i].push_back(v); } } return g; } // Function to add an edge void Graph::addEdge( int v, int w) { // Add w to v’s list adj[v].push_back(w); } // Function to fill the stack with // the vertices during DFS traversal void Graph::fillOrder( int v, bool visited[], stack< int >& Stack) { // Mark the current node as visited visited[v] = true ; // Recur for all the vertices // adjacent to this vertex list< int >::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) { if (!visited[*i]) fillOrder(*i, visited, Stack); } // All vertices reachable from // the node v are processed // Update the stack Stack.push(v); } // Function that counts the strongly // connected components in the graph void Graph::countSCCs() { stack< int > Stack; // Mark all the vertices as not // visited (For first DFS) bool * visited = new bool [V]; for ( int i = 0; i < V; i++) visited[i] = false ; // Fill vertices in the stack // according to their finishing // time for ( int i = 0; i < V; i++) { // Vertex i is not visited if (visited[i] == false ) fillOrder(i, visited, Stack); } // Create a reversed graph Graph gr = getTranspose(); // Mark all the vertices as // not visited (For second DFS) for ( int i = 0; i < V; i++) visited[i] = false ; int cnt = 0; // Now process all vertices in // order defined by Stack while (Stack.empty() == false ) { // Pop a vertex from stack int v = Stack.top(); Stack.pop(); // Get the strongly connected // component of the popped // vertex if (visited[v] == false ) { gr.DFSUtil(v, visited); cnt++; } } // Print the result cout << cnt; } // Function that counts the minimum // number of notes required with the // given criteria void solve(vector<string>& A, vector<vector<string> >& P) { Graph g(A.size()); // Used to map the strings to // their respective indices unordered_map<string, int > um; for ( int i = 0; i < A.size(); i++) { um[A[i]] = i; } // Iterate through all the edges // and add them to the graph for ( int i = 0; i < P.size(); i++) { int x = um[P[i][0]]; int y = um[P[i][1]]; g.addEdge(x, y); } // Function Call g.countSCCs(); } // Driver Code int main() { vector<string> arr = { "Beginner" , "for" , "code" , "run" , "compile" }; vector<vector<string> > P = { { "Beginner" , "for" }, { "for" , "code" }, { "code" , "run" }, { "run" , "compile" }, { "run" , "for" } }; solve(arr, P); return 0; } |
Java
// Java program for above approach import java.util.ArrayList; import java.util.*; // Structure of class Graph public class Graph{ // No. of vertices int V; // An array of adjacency lists ArrayList<ArrayList<Integer>> adj; // Constructor of the Graph Graph( int V) { this .V = V; adj = new ArrayList<>(); for ( int i = 0 ; i < V; i++) { adj.add( new ArrayList<>()); } } // Recursive function to perform the // DFS starting from v void DFSUtil( int v, boolean visited[]) { // Mark the current node as visited visited[v] = true ; // Recur for all the vertices // adjacent to this vertex for ( int i : adj.get(v)) { if (!visited[i]) DFSUtil(i, visited); } } // Function to return the reverse // (or transpose) of the graph Graph getTranspose() { Graph g = new Graph(V); for ( int v = 0 ; v < V; v++) { // Recur for all the vertices // adjacent to this vertex for ( int i : adj.get(v)) { g.adj.get(i).add(v); } } return g; } // Function to add an edge void addEdge( int v, int w) { // Add w to v’s list adj.get(v).add(w); } // Function to fill the stack with // the vertices during DFS traversal void fillOrder( int v, boolean [] visited, Stack<Integer> stack) { // Mark the current node as visited visited[v] = true ; // Recur for all the vertices // adjacent to this vertex for ( int i : adj.get(v)) { if (!visited[i]) fillOrder(i, visited, stack); } // All vertices reachable from // the node v are processed // Update the stack stack.push(v); } // Function that counts the strongly // connected components in the graph void countSCCs() { Stack<Integer> stack = new Stack<>(); // Mark all the vertices as not // visited (For first DFS) boolean [] visited = new boolean [V]; for ( int i = 0 ; i < V; i++) visited[i] = false ; // Fill vertices in the stack // according to their finishing // time for ( int i = 0 ; i < V; i++) { // Vertex i is not visited if (visited[i] == false ) fillOrder(i, visited, stack); } // Create a reversed graph Graph gr = getTranspose(); // Mark all the vertices as // not visited (For second DFS) for ( int i = 0 ; i < V; i++) visited[i] = false ; int cnt = 0 ; // Now process all vertices in // order defined by Stack while (stack.empty() == false ) { // Pop a vertex from stack int v = stack.peek(); stack.pop(); // Get the strongly connected // component of the popped // vertex if (visited[v] == false ) { gr.DFSUtil(v, visited); cnt++; } } // Print the result System.out.print(cnt); } // Function that counts the minimum // number of notes required with the // given criteria static void solve(ArrayList<String> A, ArrayList<ArrayList<String>> P) { Graph g = new Graph(A.size()); // Used to map the strings to // their respective indices HashMap<String, Integer> um = new HashMap<>(); for ( int i = 0 ; i < A.size(); i++) { um.put(A.get(i), i); } // Iterate through all the edges // and add them to the graph for ( int i = 0 ; i < P.size(); i++) { int x = um.get(P.get(i).get( 0 )); int y = um.get(P.get(i).get( 1 )); g.addEdge(x, y); } // Function Call g.countSCCs(); } // Driver code public static void main(String[] args) { ArrayList<String> arr = new ArrayList<>(); arr.add( "Beginner" ); arr.add( "for" ); arr.add( "code" ); arr.add( "run" ); arr.add( "compile" ); ArrayList<ArrayList<String> > P = new ArrayList<>(); for ( int i = 0 ; i < 5 ; i++) P.add( new ArrayList<>()); P.get( 0 ).add( "Beginner" ); P.get( 0 ).add( "for" ); P.get( 1 ).add( "for" ); P.get( 1 ).add( "code" ); P.get( 2 ).add( "code" ); P.get( 2 ).add( "run" ); P.get( 3 ).add( "run" ); P.get( 3 ).add( "compile" ); P.get( 4 ).add( "run" ); P.get( 4 ).add( "for" ); solve(arr, P); } } // This code is contributed by hritikrommie |
Python3
# Python 3 program to implement the approach # Class structure for Graph class Graph: # Constructor of the Graph def __init__( self , V): # No. of vertices self .V = V # An array of adjacency lists self .adj = [[] for i in range (V)] # Recursive function to perform the DFS starting from v def DFSUtil( self , v, visited): visited[v] = True for i in self .adj[v]: if not visited[i]: self .DFSUtil(i, visited) # Function that returns reverse (or transpose) of the graph def getTranspose( self ): g = Graph( self .V) for v in range ( self .V): for i in self .adj[v]: g.adj[i].append(v) return g # Function to add an edge to the graph def addEdge( self , v, w): self .adj[v].append(w) # Function that fills the stack with the vertices v def fillOrder( self , v, visited, stack): visited[v] = True for i in self .adj[v]: if not visited[i]: self .fillOrder(i, visited, stack) stack.append(v) # Function to count the number of strongly connected components def countSCCs( self ): stack = [] # Mark all the vertices as not visited (For first DFS) visited = [ False for i in range ( self .V)] # Fill vertices in the stack according to their finishing time for i in range ( self .V): if not visited[i]: self .fillOrder(i, visited, stack) # Create a reversed graph gr = self .getTranspose() # Mark all the vertices as not visited (For second DFS) visited = [ False for i in range ( self .V)] # Initialize the count of strongly connected components cnt = 0 # Now process all vertices in order defined by Stack while stack: # Pop a vertex from stack v = stack.pop() # Get the strongly connected component of the popped vertex if not visited[v]: gr.DFSUtil(v, visited) cnt + = 1 # Return the result return cnt # Function that counts the minimum number of notes required with the given criteria def solve(A, P): # Used to map the strings to their respective indices um = {} for i, a in enumerate (A): um[a] = i g = Graph( len (A)) # Iterate through all the edges and add them to the graph for p in P: x = um[p[ 0 ]] y = um[p[ 1 ]] g.addEdge(x, y) print (g.countSCCs()) # Driver Code arr = [ "Beginner" , "for" , "code" , "run" , "compile" ] P = [ [ "Beginner" , "for" ], [ "for" , "code" ], [ "code" , "run" ], [ "run" , "compile" ], [ "run" , "for" ] ] # Function call solve(arr, P) # This code is contributed by phasing17 |
C#
// C# code to implement the approach using System; using System.Collections.Generic; // Structure of class Graph public class Graph { // No. of vertices int V; // An array of adjacency lists List<List< int > > adj; public Graph( int V) { this .V = V; adj = new List<List< int > >(); for ( int i = 0; i < V; i++) { adj.Add( new List< int >()); } } // Recursive function to perform // the DFS starting from v void DFSUtil( int v, bool [] visited) { visited[v] = true ; foreach ( int i in adj[v]) { if (!visited[i]) { DFSUtil(i, visited); } } } // Function that returns reverse // (or transpose) of the graph Graph GetTranspose() { Graph g = new Graph(V); for ( int v = 0; v < V; v++) { foreach ( int i in adj[v]) { g.adj[i].Add(v); } } return g; } void AddEdge( int v, int w) { adj[v].Add(w); } // Function that fills the stack // with the vertices v void FillOrder( int v, bool [] visited, Stack< int > stack) { visited[v] = true ; foreach ( int i in adj[v]) { if (!visited[i]) { FillOrder(i, visited, stack); } } stack.Push(v); } // Function to count the number of // strongly connected components void CountSCCs() { Stack< int > stack = new Stack< int >(); bool [] visited = new bool [V]; for ( int i = 0; i < V; i++) { visited[i] = false ; } for ( int i = 0; i < V; i++) { if (!visited[i]) { FillOrder(i, visited, stack); } } // Create a reversed graph Graph gr = GetTranspose(); // Mark all the vertices as // not visited (For second DFS) for ( int i = 0; i < V; i++) { visited[i] = false ; } int cnt = 0; // Now process all vertices in // order defined by Stack while (stack.Count > 0) { // Pop a vertex from stack int v = stack.Peek(); stack.Pop(); // Get the strongly connected // component of the popped // vertex if (!visited[v]) { gr.DFSUtil(v, visited); cnt++; } } // Print the result Console.WriteLine(cnt); } // Function that counts the minimum // number of notes required with the // given criteria public static void Solve(List< string > A, List<List< string > > P) { Graph g = new Graph(A.Count); // Used to map the strings to // their respective indices Dictionary< string , int > um = new Dictionary< string , int >(); for ( int i = 0; i < A.Count; i++) { um[A[i]] = i; } // Iterate through all the edges // and add them to the graph for ( int i = 0; i < P.Count; i++) { int x = um[P[i][0]]; int y = um[P[i][1]]; g.AddEdge(x, y); } g.CountSCCs(); } // Driver code static void Main( string [] args) { List< string > A = new List< string >{ "Beginner" , "for" , "code" , "run" , "compile" }; List<List< string > > P = new List<List< string > >{ new List< string >{ "Beginner" , "for" }, new List< string >{ "for" , "code" }, new List< string >{ "code" , "run" }, new List< string >{ "run" , "compile" }, new List< string >{ "run" , "for" }, }; // Function call Solve(A, P); } } // This code is contributed by phasing17 |
Javascript
// JS program to implement the approach // Structure of class Graph const Graph = // Constructor of the Graph function (V) { // No. of vertices this .V = V; // An array of adjacency lists this .adj = []; for (let i = 0; i < V; i++) { this .adj.push([]); } }; // Recursive function to perform // the DFS starting from v Graph.prototype.DFSUtil = function (v, visited) { visited[v] = true ; for (let i of this .adj[v]) { if (!visited[i]) { this .DFSUtil(i, visited); } } }; // Function that returns reverse // (or transpose) of the graph Graph.prototype.getTranspose = function () { const g = new Graph( this .V); for (let v = 0; v < this .V; v++) { for (let i of this .adj[v]) { g.adj[i].push(v); } } return g; }; Graph.prototype.addEdge = function (v, w) { this .adj[v].push(w); }; // Function that fills the stack // with the vertices v Graph.prototype.fillOrder = function (v, visited, stack) { visited[v] = true ; for (let i of this .adj[v]) { if (!visited[i]) { this .fillOrder(i, visited, stack); } } stack.push(v); }; // Function to count the number of // strongly connected components Graph.prototype.countSCCs = function () { const stack = []; // Mark all the vertices as not // visited (For first DFS) const visited = Array( this .V).fill( false ); // Fill vertices in the stack // according to their finishing // time for (let i = 0; i < this .V; i++) { if (!visited[i]) { this .fillOrder(i, visited, stack); } } // Create a reversed graph const gr = this .getTranspose(); // Mark all the vertices as // not visited (For second DFS) visited.fill( false ); let cnt = 0; // Now process all vertices in // order defined by Stack while (stack.length > 0) { // Pop a vertex from stack const v = stack.pop(); // Get the strongly connected // component of the popped // vertex if (!visited[v]) { gr.DFSUtil(v, visited); cnt++; } } // Print the result console.log(cnt); }; // Function that counts the minimum // number of notes required with the // given criteria const solve = function (A, P) { // Used to map the strings to // their respective indices const um = new Map(); for (let i = 0; i < A.length; i++) { um.set(A[i], i); } const g = new Graph(A.length); // Iterate through all the edges // and add them to the graph for (let i = 0; i < P.length; i++) { const x = um.get(P[i][0]); const y = um.get(P[i][1]); g.addEdge(x, y); } g.countSCCs(); }; // Driver Code let arr = [ "Beginner" , "for" , "code" , "run" , "compile" ]; let P = [ [ "Beginner" , "for" ], [ "for" , "code" ], [ "code" , "run" ], [ "run" , "compile" ], [ "run" , "for" ] ]; // Function call solve(arr, P); // This code is contributed by phasing17 |
3
Time Complexity: O(N + M)
Auxiliary Space: O(N)