Dado un grafo dirigido de N vértices y M aristas, la tarea es encontrar el número mínimo de aristas necesarias para hacer que el grafo dado sea fuertemente conectado .
Ejemplos:
Entrada: N = 3, M = 3, origen[] = {1, 2, 1}, destino[] = {2, 3, 3}
Salida: 1
Explicación:
Agregar un borde dirigido que une el par de vértices {3, 1} hace que el gráfico sea fuertemente conexo.
Por lo tanto, el número mínimo de aristas requeridas es 1.
A continuación se muestra la ilustración del ejemplo anterior:
Entrada: N = 5, M = 5, origen[] = {1, 3, 1, 3, 4}, destino[] = {2, 2, 3, 4, 5}
Salida: 2
Explicación:
Adición de 2 aristas dirigidas unir el siguiente par de vértices hace que el gráfico sea fuertemente conexo:
- {2, 1}
- {5, 2}
Por lo tanto, el número mínimo de aristas requeridas es 2.
Enfoque:
para un gráfico fuertemente conectado , cada vértice debe tener un grado de entrada y un grado de salida de al menos 1 . Por lo tanto, para hacer un grafo fuertemente conectado, cada vértice debe tener una arista entrante y una arista saliente. El número máximo de aristas entrantes y salientes necesarias para que el gráfico esté fuertemente conectado es el mínimo de aristas necesarias para que esté fuertemente conectado.
Siga los pasos a continuación para resolver el problema:
- Encuentre el conteo de grados de entrada y salida de cada vértice del gráfico, usando DFS .
- Si el grado de entrada o de salida de un vértice es mayor que 1 , entonces considérelo como solo 1 .
- Cuente el grado total de entrada y salida del gráfico dado .
- El número mínimo de aristas necesarias para que el gráfico esté fuertemente conectado viene dado por max(N-totalIndegree, N-totalOutdegree).
- Imprime el recuento de bordes mínimos como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Perform DFS to count the in-degree
// and out-degree of the graph
void dfs(int u, vector<int> adj[], int* vis, int* inDeg,
int* outDeg)
{
// Mark the source as visited
vis[u] = 1;
// Traversing adjacent nodes
for (auto v : adj[u])
{
// Mark out-degree as 1
outDeg[u] = 1;
// Mark in-degree as 1
inDeg[v] = 1;
// If not visited
if (vis[v] == 0)
{
// DFS Traversal on
// adjacent vertex
dfs(v, adj, vis, inDeg, outDeg);
}
}
}
// Function to return minimum number
// of edges required to make the graph
// strongly connected
int findMinimumEdges(int source[], int N, int M, int dest[])
{
// For Adjacency List
vector<int> adj[N + 1];
// Create the Adjacency List
for (int i = 0; i < M; i++)
{
adj[ source[i] ].push_back(dest[i]);
}
// Initialize the in-degree array
int inDeg[N + 1] = { 0 };
// Initialize the out-degree array
int outDeg[N + 1] = { 0 };
// Initialize the visited array
int vis[N + 1] = { 0 };
// Perform DFS to count in-degrees
// and out-degreess
dfs(1, adj, vis, inDeg, outDeg);
// To store the result
int minEdges = 0;
// To store total count of in-degree
// and out-degree
int totalIndegree = 0;
int totalOutdegree = 0;
// Find total in-degree
// and out-degree
for (int i = 1; i <= N; i++)
{
if (inDeg[i] == 1)
totalIndegree++;
if (outDeg[i] == 1)
totalOutdegree++;
}
// Calculate the minimum
// edges required
minEdges = max(N - totalIndegree, N - totalOutdegree);
// Return the minimum edges
return minEdges;
}
// Driver Code
int main()
{
int N = 5, M = 5;
int source[] = { 1, 3, 1, 3, 4 };
int destination[] = { 2, 2, 3, 4, 5 };
// Function call
cout << findMinimumEdges(source, N, M, destination);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Perform DFS to count the
// in-degree and out-degree
// of the graph
static void dfs(int u, Vector<Integer> adj[],
int[] vis, int[] inDeg,
int[] outDeg)
{
// Mark the source
// as visited
vis[u] = 1;
// Traversing adjacent nodes
for (int v : adj[u])
{
// Mark out-degree as 1
outDeg[u] = 1;
// Mark in-degree as 1
inDeg[v] = 1;
// If not visited
if (vis[v] == 0)
{
// DFS Traversal on
// adjacent vertex
dfs(v, adj, vis,
inDeg, outDeg);
}
}
}
// Function to return minimum
// number of edges required
// to make the graph strongly
// connected
static int findMinimumEdges(int source[],
int N, int M,
int dest[])
{
// For Adjacency List
@SuppressWarnings("unchecked")
Vector<Integer> []adj =
new Vector[N + 1];
for (int i = 0; i < adj.length; i++)
adj[i] = new Vector<Integer>();
// Create the Adjacency List
for (int i = 0; i < M; i++)
{
adj].add(dest[i]);
}
// Initialize the in-degree array
int inDeg[] = new int[N + 1];
// Initialize the out-degree array
int outDeg[] = new int[N + 1];
// Initialize the visited array
int vis[] = new int[N + 1];
// Perform DFS to count
// in-degrees and out-degreess
dfs(1, adj, vis, inDeg, outDeg);
// To store the result
int minEdges = 0;
// To store total count of
// in-degree and out-degree
int totalIndegree = 0;
int totalOutdegree = 0;
// Find total in-degree
// and out-degree
for (int i = 1; i <= N; i++)
{
if (inDeg[i] == 1)
totalIndegree++;
if (outDeg[i] == 1)
totalOutdegree++;
}
// Calculate the minimum
// edges required
minEdges = Math.max(N - totalIndegree,
N - totalOutdegree);
// Return the minimum edges
return minEdges;
}
// Driver Code
public static void main(String[] args)
{
int N = 5, M = 5;
int source[] = {1, 3, 1, 3, 4};
int destination[] = {2, 2, 3, 4, 5};
// Function call
System.out.print(findMinimumEdges(source,
N, M,
destination));
}
}
Python3
# Python3 program to implement # the above approach # Perform DFS to count the in-degree # and out-degree of the graph def dfs(u, adj, vis,inDeg, outDeg): # Mark the source as visited vis[u] = 1; # Traversing adjacent nodes for v in adj[u]: # Mark out-degree as 1 outDeg[u] = 1; # Mark in-degree as 1 inDeg[u] = 1; # If not visited if (vis[v] == 0): # DFS Traversal on # adjacent vertex dfs(v, adj, vis, inDeg, outDeg) # Function to return minimum # number of edges required # to make the graph strongly # connected def findMinimumEdges(source, N, M, dest): # For Adjacency List adj = [[] for i in range(N + 1)] # Create the Adjacency List for i in range(M): adj].append(dest[i]); # Initialize the in-degree array inDeg = [0 for i in range(N + 1)] # Initialize the out-degree array outDeg = [0 for i in range(N + 1)] # Initialize the visited array vis = [0 for i in range(N + 1)] # Perform DFS to count in-degrees # and out-degreess dfs(1, adj, vis, inDeg, outDeg); # To store the result minEdges = 0; # To store total count of # in-degree and out-degree totalIndegree = 0; totalOutdegree = 0; # Find total in-degree # and out-degree for i in range(1, N): if (inDeg[i] == 1): totalIndegree += 1; if (outDeg[i] == 1): totalOutdegree += 1; # Calculate the minimum # edges required minEdges = max(N - totalIndegree, N - totalOutdegree); # Return the minimum edges return minEdges; # Driver code if __name__ == "__main__": N = 5 M = 5 source = [1, 3, 1, 3, 4] destination = [2, 2, 3, 4, 5] # Function call print(findMinimumEdges(source, N, M, destination)) # This code is contributed by rutvik_56
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Perform DFS to count the
// in-degree and out-degree
// of the graph
static void dfs(int u, List<int> []adj,
int[] vis, int[] inDeg,
int[] outDeg)
{
// Mark the source
// as visited
vis[u] = 1;
// Traversing adjacent nodes
foreach (int v in adj[u])
{
// Mark out-degree as 1
outDeg[u] = 1;
// Mark in-degree as 1
inDeg[v] = 1;
// If not visited
if (vis[v] == 0)
{
// DFS Traversal on
// adjacent vertex
dfs(v, adj, vis,
inDeg, outDeg);
}
}
}
// Function to return minimum
// number of edges required
// to make the graph strongly
// connected
static int findMinimumEdges(int []source,
int N, int M,
int []dest)
{
// For Adjacency List
List<int> []adj = new List<int>[N + 1];
for(int i = 0; i < adj.Length; i++)
adj[i] = new List<int>();
// Create the Adjacency List
for(int i = 0; i < M; i++)
{
adj].Add(dest[i]);
}
// Initialize the in-degree array
int []inDeg = new int[N + 1];
// Initialize the out-degree array
int []outDeg = new int[N + 1];
// Initialize the visited array
int []vis = new int[N + 1];
// Perform DFS to count
// in-degrees and out-degreess
dfs(1, adj, vis, inDeg, outDeg);
// To store the result
int minEdges = 0;
// To store total count of
// in-degree and out-degree
int totalIndegree = 0;
int totalOutdegree = 0;
// Find total in-degree
// and out-degree
for (int i = 1; i <= N; i++)
{
if (inDeg[i] == 1)
totalIndegree++;
if (outDeg[i] == 1)
totalOutdegree++;
}
// Calculate the minimum
// edges required
minEdges = Math.Max(N - totalIndegree,
N - totalOutdegree);
// Return the minimum edges
return minEdges;
}
// Driver Code
public static void Main(String[] args)
{
int N = 5, M = 5;
int []source = { 1, 3, 1, 3, 4 };
int []destination = { 2, 2, 3, 4, 5 };
// Function call
Console.Write(findMinimumEdges(source,
N, M,
destination));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to implement
// the above approach
// Perform DFS to count the
// in-degree and out-degree
// of the graph
function dfs(u, adj, vis, inDeg, outDeg)
{
// Mark the source
// as visited
vis[u] = 1;
// Traversing adjacent nodes
for(var v of adj[u])
{
// Mark out-degree as 1
outDeg[u] = 1;
// Mark in-degree as 1
inDeg[v] = 1;
// If not visited
if (vis[v] == 0)
{
// DFS Traversal on
// adjacent vertex
dfs(v, adj, vis,
inDeg, outDeg);
}
}
}
// Function to return minimum
// number of edges required
// to make the graph strongly
// connected
function findMinimumEdges(source, N, M, dest)
{
// For Adjacency List
var adj = Array.from(Array(N+1), ()=>Array());
// Create the Adjacency List
for(var i = 0; i < M; i++)
{
adj].push(dest[i]);
}
// Initialize the in-degree array
var inDeg = Array(N+1).fill(0);
// Initialize the out-degree array
var outDeg = Array(N+1).fill(0);
// Initialize the visited array
var vis = Array(N+1).fill(0);
// Perform DFS to count
// in-degrees and out-degreess
dfs(1, adj, vis, inDeg, outDeg);
// To store the result
var minEdges = 0;
// To store total count of
// in-degree and out-degree
var totalIndegree = 0;
var totalOutdegree = 0;
// Find total in-degree
// and out-degree
for (var i = 1; i <= N; i++)
{
if (inDeg[i] == 1)
totalIndegree++;
if (outDeg[i] == 1)
totalOutdegree++;
}
// Calculate the minimum
// edges required
minEdges = Math.max(N - totalIndegree,
N - totalOutdegree);
// Return the minimum edges
return minEdges;
}
// Driver Code
var N = 5, M = 5;
var source = [1, 3, 1, 3, 4];
var destination = [2, 2, 3, 4, 5];
// Function call
document.write(findMinimumEdges(source,
N, M,
destination));
</script>
Producción
2
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por tariq1510985 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA