Minimum edges required to make a Directed Graph Strongly Connected
Given a Directed graph of N vertices and M edges, the task is to find the minimum number of edges required to make the given graph Strongly Connected.
Examples:
Input: N = 3, M = 3, source[] = {1, 2, 1}, destination[] = {2, 3, 3}
Output: 1
Explanation:
Adding a directed edge joining the pair of vertices {3, 1} makes the graph strongly connected.
Hence, the minimum number of edges required is 1.
Below is the illustration of the above example:
Input: N = 5, M = 5, source[] = {1, 3, 1, 3, 4}, destination[] = {2, 2, 3, 4, 5}
Output: 2
Explanation:
Adding 2 directed edges to join the following pair of vertices makes the graph strongly connected:
- {2, 1}
- {5, 2}
Hence, the minimum number of edges required is 2.
Approach:
For a Strongly Connected Graph, each vertex must have an in-degree and an out-degree of at least 1. Therefore, in order to make a graph strongly connected, each vertex must have an incoming edge and an outgoing edge. The maximum number of incoming edges and the outgoing edges required to make the graph strongly connected is the minimum edges required to make it strongly connected.
Follow the steps below to solve the problem:
- Find the count of in-degrees and out-degrees of each vertex of the graph, using DFS.
- If the in-degree or out-degree of a vertex is greater than 1, then consider it as only 1.
- Count the total in-degree and out-degree of the given graph.
- The minimum number of edges required to make the graph strongly connected is then given by max(N-totalIndegree, N-totalOutdegree).
- Print the count of minimum edges as the result.
Below is the implementation of 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 from all unvisited vertices
for (int i = 1; i <= N; ++i)
{
if (vis[i] == 0)
{
dfs(i, 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;
}
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[source[i]].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 from all unvisited vertices
for (int i = 1; i <= N; ++i) {
if (vis[i] == 0) {
dfs(i, 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));
}
}
# 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[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
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[source[i]].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 from all unvisited vertices
for i in range(1, N + 1):
if vis[i] == 0:
dfs(i, 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 + 1):
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))
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[source[i]].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 from all unvisited vertices
for (int i = 1; i <= N; ++i) {
if (vis[i] == 0) {
dfs(i, 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));
}
}
<script>
// 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[source[i]].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 from all unvisited vertices
for (var i = 1; i <= N; i++)
{
if (vis[i] == 0)
{
dfs(i, 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>
Output
2
Time Complexity: O(N + M)
Auxiliary Space: O(N)