Dada una array arr[] que consta de N strings que representan el nombre de los estudiantes de la clase y otra array de pares P[][2] tal que a P[i][0] le gusta P[i][1] , la tarea es encontrar la cantidad mínima de notas que se distribuirán en la clase de modo que las notas se puedan compartir solo si a un estudiante le gusta otro estudiante, ya sea directa o indirectamente.
Ejemplos:
Entrada: arr[] = {geeks, for, code, run, compile}, P[][] = {{geeks, for}, {for, code}, {code, run}, {run, compile}, { ejecutar, para}}
Salida: 3
Explicación:
A continuación se muestra la imagen para representar la relación entre los estudiantes:
De la imagen de arriba:
- Los estudiantes nombrados {“for”, “code”, “run”} requieren una sola copia de las notas, ya que existe una relación mutua entre ellas.
- El estudiante llamado {“geeks”} requiere una sola copia de las notas.
- El estudiante llamado {“compilar”} también requiere una sola copia de las notas.
Entonces, el número mínimo de notas requeridas es 3.
Entrada: arr[] = {geeks, for, all, run, debug, compile}, P[][] = {{geeks, for}, {for, all}, {all, geeks}, {for, run} , {ejecutar, compilar}, {compilar, depurar}, {depurar, ejecutar}}
Salida: 2
Enfoque: El problema dado se puede resolver encontrando el número de componentes fuertemente conectados en un gráfico dirigido después de generar el gráfico de relación con las condiciones dadas. Siga los pasos a continuación para resolver el problema:
- Cree un hashmap , diga M para asignar los nombres de los estudiantes a sus respectivos valores de índice.
- Recorra la array A usando la variable i y asigne cada string A[i] en el mapa M al valor i .
- Itere todos los pares en la array P y para cada par obtenga los valores correspondientes del HashMap, M y cree un borde dirigido entre ellos.
- Después de atravesar todos los pares, se forma un gráfico dirigido que tiene N vértices y M número de aristas.
- Cree una pila vacía S y realice el recorrido DFS del gráfico :
- Cree una función recursiva que tome el índice de un Node y una array visitada.
- Marque el Node actual como visitado y recorra todos los Nodes adyacentes y no marcados y llame a la función recursiva con el índice del Node adyacente.
- Después de atravesar todos los vecinos del Node actual, inserte el Node actual en la pila S .
- Invierta las direcciones de todos los bordes para obtener la transposición del gráfico construido .
- Iterar hasta que la pila S no esté vacía y realizar los siguientes pasos:
- Almacene el elemento superior de la pila S en una variable V y sáquelo de la pila S .
- Realice el recorrido DFS desde el Node V como fuente.
- Actualice el número de componentes conectados y almacene el conteo en una variable, sat cnt .
- Después de completar los pasos anteriores, imprima el valor de cnt como resultado.
A continuación se muestra la implementación del enfoque anterior:
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;
// Recurr 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++) {
// Recurr 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;
// Recurr 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;
// Recurr 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++)
{
// Recurr 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;
// Recurr 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
Producción:
3
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por saivamshik24 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA