Horje
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[] = {geeks, for, code, run, compile}, P[][] = {{geeks, 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:

  1. Students named {“for”, “code”, “run”} require a single copy of notes, since there exists a mutual relationship between them.
  2. Student named {“geeks”} requires a single copy of notes.
  3. Student named {“compile”} also require a single copy of notes.

So, the minimum number of notes required is 3.

Input: arr[] = {geeks, for, all, run, debug, compile}, P[][] = {{geeks, for}, {for, all}, {all, geeks}, {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:

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
        = { "geeks", "for", "code",
            "run", "compile" };
    vector<vector<string> > P = { { "geeks", "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("geeks");
    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("geeks");
    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 = ["geeks", "for", "code", "run", "compile"]
P = [
    ["geeks", "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>{ "geeks", "for", "code",
                         "run", "compile" };
    List<List<string> > P = new List<List<string> >{
      new List<string>{ "geeks", "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 = [ "geeks", "for", "code", "run", "compile" ];
let P = [
    [ "geeks", "for" ], [ "for", "code" ],
    [ "code", "run" ], [ "run", "compile" ],
    [ "run", "for" ]
];
 
// Function call
solve(arr, P);
 
// This code is contributed by phasing17

Output: 

3

 

Time Complexity: O(N + M)
Auxiliary Space: O(N) 

 


 


Reffered: https://www.geeksforgeeks.org

Graph

Related
Shortest path for a thief to reach the Nth house avoiding policemen Shortest path for a thief to reach the Nth house avoiding policemen
Maximum Bitwise XOR of node values of an Acyclic Graph made up of N given vertices using M edges Maximum Bitwise XOR of node values of an Acyclic Graph made up of N given vertices using M edges
Maximum cost path from source node to destination node via at most K intermediate nodes Maximum cost path from source node to destination node via at most K intermediate nodes
Java Program to Implement of Gabow Scaling Algorithm Java Program to Implement of Gabow Scaling Algorithm
Path from a given source to a given destination having Kth largest weight in a Graph Path from a given source to a given destination having Kth largest weight in a Graph

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje