Dado un gráfico dirigido con N Nodes y M aristas en el arreglo V[] , la tarea es encontrar el número de Nodes que son accesibles desde todos los demás Nodes, es decir, tienen al menos una ruta desde todos los demás Nodes.
Ejemplos:
Entrada: N = 5 y M = 5, V = [[1, 2], [2, 3], [3, 4], [4, 3], [5, 4]]
Salida : 2
Explicación:
Podemos mire de cerca después de formar el gráfico
que el capitán américa solo puede esconderse en una
habitación 3 y 4 porque son las únicas habitaciones
que tienen puertas a través de ellas. Entonces,
la respuesta es 2.Entrada: N = 2, M = 1, V = [[1, 2]]
Salida : 1
Enfoque: Este problema se puede resolver utilizando el Algoritmo de Kosaraju para encontrar el conteo de Componentes Fuertemente Conectados basado en la siguiente idea:
Todos los Nodes de un solo componente fuertemente conectado son accesibles desde cualquier otro Node de ese componente. Si cada componente conexo se considera como un Node del gráfico, se dan los siguientes casos:
- Los componentes conectados están desconectados. Por lo tanto, más de un componente tendrá un grado superior a 0. En este caso, ningún Node es accesible desde todos los demás Nodes.
- Sólo hay un componente conectado. Esta vez, todos los Nodes son accesibles desde todos los demás Nodes.
- Hay más de un componente conectado y solo un Node tiene un grado de salida igual a 0. En este caso, solo ese Node es accesible desde todos los demás Nodes.
Siga los pasos mencionados a continuación para implementar la idea anterior:
- Encuentre todos los componentes fuertemente conectados del gráfico dado
- Cree un nuevo gráfico en el que cada componente fuertemente conectado se considere como un solo Node. (digamos que este gráfico es grrrr )
- Encuentre el número de Nodes en grrrr que tienen un grado superior ==0 (deje que este número sea x1 )
- Si x1 > 1 , la respuesta es 0 porque esto sugiere que algunos Nodes no son accesibles desde otros o que algunos componentes están desconectados.
- Si x1 = 0 , la respuesta también es 0 .
- Por lo tanto, existe solo cuando x1 = 1 y la respuesta es igual al número de Nodes en el componente fuertemente conectado que tiene un grado superior = 0 en el gráfico grrrr .
A continuación se muestra la implementación del enfoque anterior.
Java
// Java code to implement the approach
import java.io.*;
import java.util.*;
class GFG {
// Function to form the components
private static void
dfs(int node, ArrayList<ArrayList<Integer> > adj,
Stack<Integer> st, int[] vis)
{
vis[node] = 1;
for (Integer it : adj.get(node)) {
if (vis[it] == 0) {
dfs(it, adj, st, vis);
}
}
st.push(node);
}
// Function to run dfs in the
// transpose adjacency to get
// the strongly connected components
private static void
dfs_(int node, ArrayList<ArrayList<Integer> > transpose,
int[] vis, int par, int[] parent, int[] no)
{
vis[node] = 1;
parent[node] = par;
no[par]++;
for (Integer it : transpose.get(node)) {
if (vis[it] == 0) {
dfs_(it, transpose, vis, par, parent, no);
}
}
}
// Function to form the new graph using
// the strongly connected components
private static void
dfs__(int node, int[] vis,
ArrayList<ArrayList<Integer> > adj,
ArrayList<ArrayList<Integer> > adjn, int[] parent)
{
vis[node] = 1;
for (Integer it : adj.get(node)) {
int par1 = parent[node];
int par2 = parent[it];
if (par1 == par2) {
continue;
}
adjn.get(par1).add(par2);
if (vis[it] == 0) {
dfs__(it, vis, adj, adjn, parent);
}
}
}
// Function to find the total number
// of reachable nodes
public static int countReachables(int N, int M,
int V[][])
{
ArrayList<ArrayList<Integer> > adj
= new ArrayList<>();
for (int i = 0; i < N; i++) {
adj.add(new ArrayList<>());
}
// Generate the adjacency matrix
for (int i = 0; i < M; i++) {
adj.get(V[i][0] - 1).add(V[i][1] - 1);
}
int[] vis = new int[N];
// Stack to store the components
Stack<Integer> st = new Stack<>();
for (int i = 0; i < N; i++) {
if (vis[i] == 0) {
dfs(i, adj, st, vis);
}
}
ArrayList<ArrayList<Integer> > transpose
= new ArrayList<>();
for (int i = 0; i < N; i++) {
transpose.add(new ArrayList<>());
vis[i] = 0;
}
// Transpose adjacency matrix
for (int i = 0; i < M; i++) {
transpose.get(V[i][1] - 1).add(V[i][0] - 1);
}
int[] parent = new int[N];
int par = 0;
int[] no = new int[N];
while (!st.isEmpty()) {
int node = st.pop();
if (vis[node] == 0) {
dfs_(node, transpose, vis, par, parent, no);
par++;
}
}
// Adjacency matrix to represent the graph
// where each node is a strongly connected component
ArrayList<ArrayList<Integer> > adjn
= new ArrayList<>();
for (int i = 0; i < par; i++) {
adjn.add(new ArrayList<>());
}
Arrays.fill(vis, 0);
for (int i = 0; i < N; i++) {
if (vis[i] == 0) {
dfs__(i, vis, adj, adjn, parent);
}
}
// Check nodes with outdegree 0
int outDegree = 0;
for (int i = 0; i < par; i++) {
if (adjn.get(i).size() == 0) {
outDegree++;
}
}
// Decide the count based on the conditions
if (outDegree > 1 || outDegree == 0) {
return 0;
}
else {
for (int i = 0; i < par; i++) {
if (adjn.get(i).size() == 0) {
return no[i];
}
}
}
return -1;
}
// Driver code
public static void main(String[] args)
{
int N = 5;
int M = 5;
int V[][] = new int[M + 1][2];
V[0][0] = 1;
V[0][1] = 2;
V[1][0] = 2;
V[1][1] = 3;
V[2][0] = 3;
V[2][1] = 4;
V[3][0] = 4;
V[3][1] = 3;
V[4][0] = 5;
V[4][1] = 4;
// Function call
int ans = countReachables(N, M, V);
System.out.println(ans);
}
}
2
Complejidad Temporal: O(N+M)
Espacio Auxiliar:O(N+M)
Publicación traducida automáticamente
Artículo escrito por ishankhandelwals y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA