Find all the Mother Vertices of a graph

0 0 11 minutes read

Mother vertex: A mother vertex in a Graph G = (V, E) is a vertex v such that all other vertices in G can be reached by a path from v. There can be zero, one, or more than one mother vertices in a graph. We need to find all the mother vertices in the given graph.

Example :

Input : Given graph below
Output : 0 1 4
Explanation : In the given graph, the mother vertices are 0, 1 and 4 as there exists a path to each vertex from these vertices.

Naive approach :
A trivial approach will be to perform a DFS or a BFS on all the vertices and find whether we can reach all the vertices from that vertex.

Time Complexity: O(V(E+V))

Efficient Approach :

Find any mother vertex v in the given graph G using this algorithm.
If a mother vertex exists, then the set of vertices of Graph G that form a strongly connected component and contains v is the set of all the mother vertices of the graph.

How does the above idea work?
If a mother vertex exists for a graph, then all the mother vertices are the vertices of the strongly connected component which contains the mother vertex because if v is a mother vertex and there exists a path from u->v then u must be a mother vertex as well.

Below is the implementation of the above approach :

C++

// C++ program to find all the mother vertices
#include <bits/stdc++.h>
using namespace std;
 
// This function does DFS traversal
// from given node u, and marks the
// visited nodes in the visited array
void dfs_helper(int u, vector<vector<int> >& adj,
                bool visited[])
{
    if (visited[u])
        return;
 
    visited[u] = true;
 
    for (auto v : adj[u]) {
        if (!visited[v])
            dfs_helper(v, adj, visited);
    }
}
 
// Function that stores the adjacency
// list of the transpose graph of the 
// given graph in the trans_adj vector
void getTransposeGraph(vector<vector<int> >& adj,
                       vector<vector<int> >& trans_adj)
{
    for (int u = 0; u < adj.size(); u++) {
        for (auto v : adj[u]) {
            trans_adj[v].push_back(u);
        }
    }
}
 
// Initializes all elements of visited
// array with value false
void initialize_visited(bool visited[], int n)
{
    for (int u = 0; u < n; u++)
        visited[u] = false;
}
 
// Returns the list of mother 
// vertices. If the mother vertex 
// does not exists returns -1
vector<int> findAllMotherVertices(vector<vector<int> >& adj)
{
    int n = adj.size();
    bool visited[n];
 
    // Find any mother vertex 
      // in given graph, G
    initialize_visited(visited, n);
    int last_dfs_called_on = -1;
 
    for (int u = 0; u < n; u++) {
        if (!visited[u]) {
            dfs_helper(u, adj, visited);
            last_dfs_called_on = u;
        }
    }
 
    // Check if we can reach 
    // all vertices from 
    // last_dfs_called_on node
    initialize_visited(visited, n);
    dfs_helper(last_dfs_called_on, adj, visited);
 
    for (int u = 0; u < n; u++) {
         
          // Check if the mother vertex
        // exist else return -1
          if (!visited[u]) {
            vector<int> emptyVector;
            emptyVector.push_back(-1);
 
            return emptyVector;
        }
    }
 
    // Now in G_transpose, do DFS 
    // from that mother vertex, 
    // and we will only reach the 
      // other mother vertices of G
    int motherVertex = last_dfs_called_on;
 
    // trans_adj is the transpose
    // of the given Graph
    vector<vector<int> > trans_adj(n);
 
    // Function call to get 
      // the transpose graph
    getTransposeGraph(adj, trans_adj);
 
    // DFS from that mother vertex
    // in the transpose graph and the 
    // visited nodes are all the 
    // mother vertices of the given 
    // graph G
    initialize_visited(visited, n);
    dfs_helper(motherVertex, trans_adj, visited);
 
    // Vector to store the list 
      // of mother vertices
    vector<int> ans;
 
    for (int u = 0; u < n; u++) {
        if (visited[u])
            ans.push_back(u);
    }
 
    // Return the required list
    return ans;
}
 
// Driver Code
int main()
{
    // No. of nodes
    int V = 8;
    vector<vector<int> > adj(V);
 
    adj[0].push_back(1);
    adj[1].push_back(2);
    adj[1].push_back(4);
    adj[1].push_back(5);
    adj[2].push_back(3);
    adj[2].push_back(6);
    adj[3].push_back(2);
    adj[3].push_back(7);
    adj[4].push_back(0);
    adj[4].push_back(5);
    adj[5].push_back(6);
    adj[6].push_back(5);
    adj[6].push_back(7);
 
    // Function call to find the mother vertices
    vector<int> motherVertices = findAllMotherVertices(adj);
 
    // Print answer
    if (motherVertices[0] == -1)
        cout << "No mother vertex exists";
    else {
        cout << "All Mother vertices of the graph are : ";
        for (int v : motherVertices)
            cout << v << " ";
    }
 
    return 0;
}

Java

// Java program to find all the mother vertices
import java.util.*;
 
class GFG{
 
// This function does DFS traversal
// from given node u, and marks the
// visited nodes in the visited array
static void dfs_helper(int u, Vector<Integer>[] adj,
                boolean visited[])
{
    if (visited[u])
        return;
 
    visited[u] = true;
 
    for (int v : adj[u]) {
        if (!visited[v])
            dfs_helper(v, adj, visited);
    }
}
 
// Function that stores the adjacency
// list of the transpose graph of the 
// given graph in the trans_adj vector
static void getTransposeGraph(Vector<Integer>[] adj,
        Vector<Integer>[] trans_adj)
{
    for (int u = 0; u < adj.length; u++) {
        for (int v : adj[u]) {
            trans_adj[v].add(u);
        }
    }
}
 
// Initializes all elements of visited
// array with value false
static void initialize_visited(boolean visited[], int n)
{
    for (int u = 0; u < n; u++)
        visited[u] = false;
}
 
// Returns the list of mother 
// vertices. If the mother vertex 
// does not exists returns -1
static Vector<Integer> findAllMotherVertices(Vector<Integer>[] adj)
{
    int n = adj.length;
    boolean []visited = new boolean[n];
 
    // Find any mother vertex 
      // in given graph, G
    initialize_visited(visited, n);
    int last_dfs_called_on = -1;
 
    for (int u = 0; u < n; u++) {
        if (!visited[u]) {
            dfs_helper(u, adj, visited);
            last_dfs_called_on = u;
        }
    }
 
    // Check if we can reach 
       // all vertices from 
    // last_dfs_called_on node
    initialize_visited(visited, n);
    dfs_helper(last_dfs_called_on, adj, visited);
 
    for (int u = 0; u < n; u++) {
         
          // Check of the mother vertex
        // exist else return -1
          if (!visited[u]) {
            Vector<Integer> emptyVector = new Vector<Integer>();
            emptyVector.add(-1);
 
            return emptyVector;
        }
    }
 
    // Now in G_transpose, do DFS 
    // from that mother vertex, 
    // and we will only reach the 
      // other mother vertices of G
    int motherVertex = last_dfs_called_on;
 
    // trans_adj is the transpose
    // of the given Graph
    Vector<Integer> []trans_adj = new Vector[n];
    for (int i = 0; i < trans_adj.length; i++)
        trans_adj[i] = new Vector<Integer>();
 
    // Function call to get 
      // the transpose graph
    getTransposeGraph(adj, trans_adj);
 
    // DFS from that mother vertex
    // in the transpose graph and the 
    // visited nodes are all the 
    // mother vertices of the given 
    // graph G
    initialize_visited(visited, n);
    dfs_helper(motherVertex, trans_adj, visited);
 
    // Vector to store the list 
      // of mother vertices
    Vector<Integer> ans = new Vector<Integer>();
 
    for (int u = 0; u < n; u++) {
        if (visited[u])
            ans.add(u);
    }
 
    // Return the required list
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    // No. of nodes
    int V = 8;
    Vector<Integer>[] adj = new Vector[V];
    for (int i = 0; i < adj.length; i++)
        adj[i] = new Vector<Integer>();
    adj[0].add(1);
    adj[1].add(2);
    adj[1].add(4);
    adj[1].add(5);
    adj[2].add(3);
    adj[2].add(6);
    adj[3].add(2);
    adj[3].add(7);
    adj[4].add(0);
    adj[4].add(5);
    adj[5].add(6);
    adj[6].add(5);
    adj[6].add(7);
 
    // Function call to find the mother vertices
    Vector<Integer> motherVertices = findAllMotherVertices(adj);
 
    // Print answer
    if (motherVertices.get(0) == -1)
        System.out.print("No mother vertex exists");
    else {
        System.out.print("All Mother vertices of the graph are : ");
        for (int v : motherVertices)
            System.out.print(v+ " ");
    }
 
}
}
 
// This code is contributed by 29AjayKumar

Python

from typing import List
 
# This function does DFS traversal
# from given node u, and marks the
# visited nodes in the visited array
def dfs_helper(u, adj, visited):
    if visited[u]:
        return
 
    visited[u] = True
 
    for v in adj[u]:
        if not visited[v]:
            dfs_helper(v, adj, visited)
 
# Function that stores the adjacency
# list of the transpose graph of the 
# given graph in the trans_adj list
def getTransposeGraph(adj):
    n = len(adj)
    trans_adj = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]:
            trans_adj[v].append(u)
    return trans_adj
 
# Initializes all elements of visited
# array with value False
def initialize_visited(n):
    return [False for _ in range(n)]
 
# Returns the list of mother 
# vertices. If the mother vertex 
# does not exist returns -1
def findAllMotherVertices(adj):
    n = len(adj)
    visited = initialize_visited(n)
 
    # Find any mother vertex 
    # in given graph, G
    last_dfs_called_on = -1
 
    for u in range(n):
        if not visited[u]:
            dfs_helper(u, adj, visited)
            last_dfs_called_on = u
 
    # Check if we can reach 
    # all vertices from 
    # last_dfs_called_on node
    visited = initialize_visited(n)
    dfs_helper(last_dfs_called_on, adj, visited)
 
    for u in range(n):
        # Check if the mother vertex
        # exists else return -1
        if not visited[u]:
            return [-1]
 
    # Now in G_transpose, do DFS 
    # from that mother vertex, 
    # and we will only reach the 
    # other mother vertices of G
    motherVertex = last_dfs_called_on
 
    # trans_adj is the transpose
    # of the given Graph
    trans_adj = getTransposeGraph(adj)
 
    # DFS from that mother vertex
    # in the transpose graph and the 
    # visited nodes are all the 
    # mother vertices of the given 
    # graph G
    visited = initialize_visited(n)
    dfs_helper(motherVertex, trans_adj, visited)
 
    # List to store the list 
    # of mother vertices
    ans = []
 
    for u in range(n):
        if visited[u]:
            ans.append(u)
 
    # Return the required list
    return ans
 
# Driver Code
if __name__ == '__main__':
    # No. of nodes
    V = 8
    adj = [[] for _ in range(V)]
 
    adj[0].append(1)
    adj[1].append(2)
    adj[1].append(4)
    adj[1].append(5)
    adj[2].append(3)
    adj[2].append(6)
    adj[3].append(2)
    adj[3].append(7)
    adj[4].append(0)
    adj[4].append(5)
    adj[5].append(6)
    adj[6].append(5)
    adj[6].append(7)
 
    # Function call to find the mother vertices
    motherVertices = findAllMotherVertices(adj)
 
    # Print answer
    if motherVertices[0] == -1:
        print("No mother vertex exists")
    else:
        print("All Mother vertices of the graph are : ")
        for v in motherVertices:
            print(v)
    

C#

// C# program to find all the mother vertices
using System;
using System.Collections.Generic;
 
class Graph {
  public int V;
  public List<List<int> > adj;
 
  public Graph(int V)
  {
    this.V = V;
    adj = new List<List<int> >(V);
    for (int i = 0; i < V; i++)
      adj.Add(new List<int>());
  }
 
  public void addEdge(int u, int v) { adj[u].Add(v); }
   
  // This function does DFS traversal
  // from given node u, and marks the
  // visited nodes in the visited array
  void dfs_helper(int u, List<List<int> > adj,
                  bool[] visited)
  {
    if (visited[u])
      return;
    visited[u] = true;
    foreach(var v in adj[u])
    {
      if (!visited[v])
        dfs_helper(v, adj, visited);
    }
  }
   
  // Function that stores the adjacency
  // list of the transpose graph of the
  // given graph in the trans_adj vector
  void getTransposeGraph(List<List<int> > adj,
                         List<List<int> > trans_adj)
  {
    for (int u = 0; u < adj.Count; u++) {
      foreach(var v in adj[u])
      {
        trans_adj[v].Add(u);
      }
    }
  }
   
  // Initializes all elements of visited
  // array with value false
  void initialize_visited(bool[] visited, int n)
  {
    for (int u = 0; u < n; u++)
      visited[u] = false;
  }
   
  // Returns the list of mother
  // vertices. If the mother vertex
  // does not exists returns -1
  public List<int> findAllMotherVertices()
  {
    bool[] visited = new bool[V];
    initialize_visited(visited, V);
     
    // Find any mother vertex
    // in given graph, G
    int last_dfs_called_on = -1;
    for (int u = 0; u < V; u++) {
      if (!visited[u]) {
        dfs_helper(u, adj, visited);
        last_dfs_called_on = u;
      }
    }
     
    // Check if we can reach
    // all vertices from
    // last_dfs_called_on node
    initialize_visited(visited, V);
    dfs_helper(last_dfs_called_on, adj, visited);
    for (int u = 0; u < V; u++) {
       
      // Check if the mother vertex
      // exist else return -1
      if (!visited[u]) {
 
        List<int> emptyList = new List<int>();
        emptyList.Add(-1);
        return emptyList;
      }
    }
 
    // Now in G_transpose, do DFS
    // from that mother vertex,
    // and we will only reach the
    // other mother vertices of G
    int motherVertex = last_dfs_called_on;
 
    // trans_adj is the transpose
    // of the given Graph
    List<List<int> > trans_adj
      = new List<List<int> >(V);
    for (int i = 0; i < V; i++)
      trans_adj.Add(new List<int>());
 
    // Function call to get
    // the transpose graph
    getTransposeGraph(adj, trans_adj);
 
    // DFS from that mother vertex
    // in the transpose graph and the
    // visited nodes are all the
    // mother vertices of the given
    // graph G
    initialize_visited(visited, V);
    dfs_helper(motherVertex, trans_adj, visited);
 
    // Vector to store the list
    // of mother vertices
    List<int> ans = new List<int>();
    for (int u = 0; u < V; u++) {
      if (visited[u])
        ans.Add(u);
    }
 
    // Return the required list
    return ans;
  }
}
 
class Program {
  public static void Main()
  {
    int V = 8;
    Graph g = new Graph(V);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(1, 4);
    g.addEdge(1, 5);
    g.addEdge(2, 3);
    g.addEdge(2, 6);
    g.addEdge(3, 2);
    g.addEdge(3, 7);
    g.addEdge(4, 0);
    g.addEdge(4, 5);
    g.addEdge(5, 6);
    g.addEdge(6, 5);
    g.addEdge(6, 7);
    // Function call to find the mother vertices
    List<int> motherVertices
      = g.findAllMotherVertices();
    if (motherVertices[0] == -1)
      Console.WriteLine("No mother vertex exists");
    else {
      Console.Write(
        "All Mother vertices of the graph are : ");
      foreach(var v in motherVertices)
        Console.Write(v + " ");
    }
  }
}

Javascript

<script>
// Javascript program to find all the mother vertices
 
// This function does DFS traversal
// from given node u, and marks the
// visited nodes in the visited array
function dfs_helper(u, adj, visited) {
  if (visited[u]) return;
 
  visited[u] = true;
 
  for (let v of adj[u]) {
    if (!visited[v]) dfs_helper(v, adj, visited);
  }
}
 
// Function that stores the adjacency
// list of the transpose graph of the
// given graph in the trans_adj vector
function getTransposeGraph(adj, trans_adj) {
  for (let u = 0; u < adj.length; u++) {
    for (let v of adj[u]) {
      trans_adj[v].push(u);
    }
  }
}
 
// Initializes all elements of visited
// array with value false
function initialize_visited(visited, n) {
  for (let u = 0; u < n; u++) visited[u] = false;
}
 
// Returns the list of mother
// vertices. If the mother vertex
// does not exists returns -1
function findAllMotherVertices(adj) {
  let n = adj.length;
  let visited = new Array(n);
 
  // Find any mother vertex
  // in given graph, G
  initialize_visited(visited, n);
  let last_dfs_called_on = -1;
 
  for (let u = 0; u < n; u++) {
    if (!visited[u]) {
      dfs_helper(u, adj, visited);
      last_dfs_called_on = u;
    }
  }
 
  // Check if we can reach
  // all vertices from
  // last_dfs_called_on node
  initialize_visited(visited, n);
  dfs_helper(last_dfs_called_on, adj, visited);
 
  for (let u = 0; u < n; u++) {
    // Check of the mother vertex
    // exist else return -1
    if (!visited[u]) {
      let emptyVector = [];
      emptyVector.push(-1);
 
      return emptyVector;
    }
  }
 
  // Now in G_transpose, do DFS
  // from that mother vertex,
  // and we will only reach the
  // other mother vertices of G
  let motherVertex = last_dfs_called_on;
 
  // trans_adj is the transpose
  // of the given Graph
  let trans_adj = new Array(n).fill(0).map(() => []);
 
  // Function call to get
  // the transpose graph
  getTransposeGraph(adj, trans_adj);
 
  // DFS from that mother vertex
  // in the transpose graph and the
  // visited nodes are all the
  // mother vertices of the given
  // graph G
  initialize_visited(visited, n);
  dfs_helper(motherVertex, trans_adj, visited);
 
  // Vector to store the list
  // of mother vertices
  let ans = [];
 
  for (let u = 0; u < n; u++) {
    if (visited[u]) ans.push(u);
  }
 
  // Return the required list
  return ans;
}
 
// Driver Code
 
// No. of nodes
let V = 8;
let adj = new Array(V).fill(0).map(() => []);
 
adj[0].push(1);
adj[1].push(2);
adj[1].push(4);
adj[1].push(5);
adj[2].push(3);
adj[2].push(6);
adj[3].push(2);
adj[3].push(7);
adj[4].push(0);
adj[4].push(5);
adj[5].push(6);
adj[6].push(5);
adj[6].push(7);
 
// Function call to find the mother vertices
let motherVertices = findAllMotherVertices(adj);
 
// Print answer
if (motherVertices[0] == -1) document.write("No mother vertex exists");
else {
  document.write("All Mother vertices of the graph are : ");
  for (let v of motherVertices) document.write(v + " ");
}
 
// This code is contributed by _saurabh_jaiswal.
</script>

Output

All Mother vertices of the graph are : 0 1 4

Time Complexity: O(V+E)
Space Complexity: O(V+E)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!