Open In App

Find a Mother Vertex in a Graph

Last Updated : 26 Feb, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Write a function to find a mother vertex in the graph.

What is a 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

Example: 

Mother-Vertex-in-a-Graph

Input: Graph as shown above

Output: 5

Note: There can be more than one mother vertices in a graph. We need to output anyone of them. 
For example, in the below graph, vertices 0, 1, and 2 are mother vertices.

Mother-vertices

Recommended Practice

Naive Approach: To solve the problem follow the below idea:

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

Time Complexity: O(V * (E+V))
Auxiliary Space: O(1) It will be O(V) if the stack space for DFS is considered or if we use a BFS.

Find a Mother Vertex in a Graph using Kosaraju’s algorithm for strongly connected component:

To solve the problem follow the below idea:

The idea is based on Kosaraju’s Strongly Connected Component Algorithm. In a graph of strongly connected components, mother vertices are always vertices of the source components in the component graph. The idea is based on the below fact:

If there exists a mother vertex (or vertices), then one of the mother vertices is the last finished vertex in DFS. (Or a mother vertex has the maximum finish time in DFS traversal). A vertex is said to be finished in DFS if a recursive call for its DFS is over, i.e., all descendants of the vertex have been visited. 

How does the above idea work? 

Let the last finished vertex be v. Basically, we need to prove that there cannot be an edge from another vertex u to v if u is not another mother vertex (Or there cannot exist a non-mother vertex u such that u-?v is an edge). There can be two possibilities.

  • A recursive DFS call is made for u before v. If an edge u-?v exists, then v must have finished before u because v is reachable through u and a vertex finishes after all its descendants.
  • A recursive DFS call is made for v before u. In this case also, if an edge u-?v exists, then either v must finish before u (which contradicts our assumption that v is finished at the end) OR u should be reachable from v (which means u is another mother vertex).

Follow the given steps to solve the problem:

  • Do DFS traversal of the given graph. While doing traversal keep track of the last finished vertex ‘v’. This step takes O(V+E) time.
  • If there exists a mother vertex (or vertices), then v must be one (or one of them). Check if v is a mother vertex by doing DFS/BFS from v. This step also takes O(V+E) time.

Below is the implementation of the above approach.

C++




// C++ program to find a mother vertex in O(V+E) time
#include <bits/stdc++.h>
using namespace std;
 
class Graph {
    int V; // No. of vertices
    list<int>* adj; // adjacency lists
 
    // A recursive function to print DFS starting from v
    void DFSUtil(int v, vector<bool>& visited);
 
public:
    Graph(int V);
    void addEdge(int v, int w);
    int findMother();
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
 
// A recursive function to print DFS starting from v
void Graph::DFSUtil(int v, vector<bool>& visited)
{
    // Mark the current node as visited and print it
    visited[v] = true;
 
    // Recur 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);
}
 
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}
 
// Returns a mother vertex if exists. Otherwise returns -1
int Graph::findMother()
{
    // visited[] is used for DFS. Initially all are
    // initialized as not visited
    vector<bool> visited(V, false);
 
    // To store last finished vertex (or mother vertex)
    int v = 0;
 
    // Do a DFS traversal and find the last finished
    // vertex
    for (int i = 0; i < V; i++) {
        if (visited[i] == false) {
            DFSUtil(i, visited);
            v = i;
        }
    }
 
    // If there exist mother vertex (or vertices) in given
    // graph, then v must be one (or one of them)
 
    // Now check if v is actually a mother vertex (or graph
    // has a mother vertex).  We basically check if every
    // vertex is reachable from v or not.
 
    // Reset all values in visited[] as false and do
    // DFS beginning from v to check if all vertices are
    // reachable from it or not.
    fill(visited.begin(), visited.end(), false);
    DFSUtil(v, visited);
    for (int i = 0; i < V; i++)
        if (visited[i] == false)
            return -1;
 
    return v;
}
 
// Driver code
int main()
{
    // Create a graph given in the above diagram
    Graph g(7);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(4, 1);
    g.addEdge(6, 4);
    g.addEdge(5, 6);
    g.addEdge(5, 2);
    g.addEdge(6, 0);
 
      // Function call
    cout << "A mother vertex is " << g.findMother();
 
    return 0;
}


Java




// Java program to find a mother
// vertex in O(V+E) time
import java.util.*;
 
class GFG {
 
    static void addEdge(int u, int v,
                        ArrayList<ArrayList<Integer> > adj)
    {
        adj.get(u).add(v);
    }
 
    // A recursive function to print DFS starting from v
    static void DFSUtil(ArrayList<ArrayList<Integer> > g,
                        int v, boolean[] visited)
    {
        // Mark the current node as
        // visited and print it
        visited[v] = true;
 
        // Recur for all the vertices
        // adjacent to this vertex
        for (int x : g.get(v)) {
            if (!visited[x]) {
                DFSUtil(g, x, visited);
            }
        }
    }
 
    // Returns a mother vertex if exists.
    // Otherwise returns -1
    static int
    motherVertex(ArrayList<ArrayList<Integer> > g, int V)
    {
 
        // visited[] is used for DFS. Initially
        // all are initialized as not visited
        boolean[] visited = new boolean[V];
 
        // To store last finished vertex
        // (or mother vertex)
        int v = -1;
 
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                DFSUtil(g, i, visited);
                v = i;
            }
        }
 
        // If there exist mother vertex (or vertices)
        // in given graph, then v must be one
        // (or one of them)
 
        // Now check if v is actually a mother
        // vertex (or graph has a mother vertex).
        // We basically check if every vertex
        // is reachable from v or not.
 
        // Reset all values in visited[] as false
        // and do DFS beginning from v to check
        // if all vertices are reachable from
        // it or not.
        boolean[] check = new boolean[V];
        DFSUtil(g, v, check);
        for (boolean val : check) {
            if (!val) {
                return -1;
            }
        }
        return v;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int V = 7;
        int E = 8;
 
        ArrayList<ArrayList<Integer> > adj
            = new ArrayList<ArrayList<Integer> >();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<Integer>());
        }
        addEdge(0, 1, adj);
        addEdge(0, 2, adj);
        addEdge(1, 3, adj);
        addEdge(4, 1, adj);
        addEdge(6, 4, adj);
        addEdge(5, 6, adj);
        addEdge(5, 2, adj);
        addEdge(6, 0, adj);
 
          // Function call
        System.out.println("A mother vertex is "
                           + motherVertex(adj, V));
    }
}
 
// This code is contributed by Tanay Shah


Python3




# Python3 program to find a mother vertex in O(V+E) time
from collections import defaultdict
 
# This class represents a directed graph using adjacency list
# representation
 
 
class Graph:
 
    def __init__(self, vertices):
        self.V = vertices  # No. of vertices
        self.graph = defaultdict(list# default dictionary
 
    # A recursive function to print DFS starting from v
    def DFSUtil(self, v, visited):
 
        # Mark the current node as visited and print it
        visited[v] = True
 
        # Recur for all the vertices adjacent to this vertex
        for i in self.graph[v]:
            if visited[i] == False:
                self.DFSUtil(i, visited)
 
    # Add w to the list of v
    def addEdge(self, v, w):
        self.graph[v].append(w)
 
    # Returns a mother vertex if exists. Otherwise returns -1
    def findMother(self):
 
        # visited[] is used for DFS. Initially all are
        # initialized as not visited
        visited = [False]*(self.V)
 
        # To store last finished vertex (or mother vertex)
        v = 0
 
        # Do a DFS traversal and find the last finished
        # vertex
        for i in range(self.V):
            if visited[i] == False:
                self.DFSUtil(i, visited)
                v = i
 
        # If there exist mother vertex (or vertices) in given
        # graph, then v must be one (or one of them)
 
        # Now check if v is actually a mother vertex (or graph
        # has a mother vertex). We basically check if every vertex
        # is reachable from v or not.
 
        # Reset all values in visited[] as false and do
        # DFS beginning from v to check if all vertices are
        # reachable from it or not.
        visited = [False]*(self.V)
        self.DFSUtil(v, visited)
        if any(i == False for i in visited):
            return -1
        else:
            return v
 
 
# Driver code
if __name__ == '__main__':
  g = Graph(7)
  g.addEdge(0, 1)
  g.addEdge(0, 2)
  g.addEdge(1, 3)
  g.addEdge(4, 1)
  g.addEdge(6, 4)
  g.addEdge(5, 6)
  g.addEdge(5, 2)
  g.addEdge(6, 0)
 
  # Function call
  print("A mother vertex is " + str(g.findMother()))
 
# This code is contributed by Neelam Yadav


C#




// C# program to find a mother
// vertex in O(V+E) time
using System;
using System.Collections.Generic;
 
class GFG {
 
    static void addEdge(int u, int v, List<List<int> > adj)
    {
        adj[u].Add(v);
    }
 
    // A recursive function to print DFS starting from v
    static void DFSUtil(List<List<int> > g, int v,
                        bool[] visited)
    {
        // Mark the current node as
        // visited and print it
        visited[v] = true;
 
        // Recur for all the vertices
        // adjacent to this vertex
        foreach(int x in g[v])
        {
            if (!visited[x]) {
                DFSUtil(g, x, visited);
            }
        }
    }
 
    // Returns a mother vertex if exists.
    // Otherwise returns -1
    static int motherVertex(List<List<int> > g, int V)
    {
 
        // visited[] is used for DFS. Initially
        // all are initialized as not visited
        bool[] visited = new bool[V];
 
        // To store last finished vertex
        // (or mother vertex)
        int v = -1;
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                DFSUtil(g, i, visited);
                v = i;
            }
        }
 
        // If there exist mother vertex (or vertices)
        // in given graph, then v must be one
        // (or one of them)
 
        // Now check if v is actually a mother
        // vertex (or graph has a mother vertex).
        // We basically check if every vertex
        // is reachable from v or not.
 
        // Reset all values in visited[] as false
        // and do DFS beginning from v to check
        // if all vertices are reachable from
        // it or not.
        bool[] check = new bool[V];
        DFSUtil(g, v, check);
        foreach(bool val in check)
        {
            if (!val) {
                return -1;
            }
        }
        return v;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int V = 7;
       // int E = 8;
        List<List<int> > adj = new List<List<int> >();
        for (int i = 0; i < V; i++) {
            adj.Add(new List<int>());
        }
        addEdge(0, 1, adj);
        addEdge(0, 2, adj);
        addEdge(1, 3, adj);
        addEdge(4, 1, adj);
        addEdge(6, 4, adj);
        addEdge(5, 6, adj);
        addEdge(5, 2, adj);
        addEdge(6, 0, adj);
 
          // Function call
        Console.WriteLine("A mother vertex is "
                          + motherVertex(adj, V));
    }
}
 
// This code is contributed by Rajput-Ji


Javascript




<script>
    // Javascript program to find a mother
    // vertex in O(V+E) time
     
    function addEdge(u, v, adj)
    {
        adj[u].push(v);
    }
 
    // A recursive function to print DFS starting from v
    function DFSUtil(g, v, visited)
    {
        // Mark the current node as
        // visited and print it
        visited[v] = true;
 
        // Recur for all the vertices
        // adjacent to this vertex
        for(let x in g[v])
        {
            if (!visited[x])
            {
                DFSUtil(g, x, visited);
            }
        }
    }
 
    // Returns a mother vertex if exists.
    // Otherwise returns -1
    function motherVertex(g, V)
    {
 
        // visited[] is used for DFS. Initially
        // all are initialized as not visited
        let visited = new Array(V);
        for(let i = 0; i < V; i++)
        {
            visited[i] = false;
        }
         
        // To store last finished vertex
        // (or mother vertex)
        let v = -1; 
        for(let i = 0; i < V; i++)
        {
            if (!visited[i])
            {
                DFSUtil(g, i, visited);
                v = i;
            }
        }
 
        // If there exist mother vertex (or vertices)
        // in given graph, then v must be one
        // (or one of them)
 
        // Now check if v is actually a mother
        // vertex (or graph has a mother vertex).
        // We basically check if every vertex
        // is reachable from v or not.
 
        // Reset all values in visited[] as false
        // and do DFS beginning from v to check
        // if all vertices are reachable from
        // it or not.
        let check = new Array(V);
        for(let i = 0; i < V; i++)
        {
            check[i] = false;
        }
        DFSUtil(g, v, check);
        for(let val in check)
        {
            if (!val)
            {
                return -1;
            }
        }
        return v-1;
    }
     
    let V = 7;
    let E = 8;  
    let adj = [];
    for(let i = 0; i < V; i++)
    {
        adj.push([]);
    }
    addEdge(0, 1,adj);
    addEdge(0, 2,adj);
    addEdge(1, 3,adj);
    addEdge(4, 1,adj);
    addEdge(6, 4,adj);
    addEdge(5, 6,adj);
    addEdge(5, 2,adj);
    addEdge(6, 0,adj);
      
    document.write("A mother vertex is " + motherVertex(adj, V));
 
// This code is contributed by divyesh072019.
</script>


Output

A mother vertex is 5


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



Similar Reads

Find a Mother vertex in a Graph using Bit Masking
A mother vertex in a Graph G = (V, E) is a vertex v such that a path from v can reach all other vertices in G by a path from v. Example: Input: Output: 5 Approach:We can solve this problem using Depth First Search approach. To further optimize our approach, we will use an efficient solution. The below solution is also using Depth First Search to so
15+ min read
Check if incoming edges in a vertex of directed graph is equal to vertex itself or not
Given a directed Graph G(V, E) with V vertices and E edges, the task is to check that for all vertices of the given graph, the incoming edges in a vertex is equal to the vertex itself or not. Examples: Input: Output: Yes Explanation: For vertex 0 there are 0 incoming edges, for vertex 1 there is 1 incoming edge. Same for vertex 2 nd 3. Approach: Th
6 min read
Check if vertex X lies in subgraph of vertex Y for the given Graph
Given an undirected graph and two vertices X and Y, our task is to check whether the vertex X lies in the subgraph of the vertex Y. Examples: Input: X = 2, Y = 3 Output: No Explanation: Subgraph of a vertex Y = 3 is set of all the vertex which lies below Y and are reachable by Y. Here subgraph of 3 contains {6} not 2. Input: X = 6, Y = 1 Output: Ye
10 min read
Check if every vertex triplet in graph contains two vertices connected to third vertex
Given an undirected graph with N vertices and K edges, the task is to check if for every combination of three vertices in the graph, there exists two vertices which are connected to third vertex. In other words, for every vertex triplet (a, b, c), if there exists a path between a and c, then there should also exist a path between b and c. Examples:
9 min read
Find the vertex diagonally opposite to the vertex M from an N-sided polygon
Given two integers N and M, the task is to find the vertex diagonally opposite to the Mth vertex of an N-sided polygon. Examples: Input: N = 6, M = 2 Output: 5 Explanation: It can be observed from the image above that the vertex opposite to vertex 5 is 2. Input: N = 8, M = 5 Output: 1 Explanation: It can be observed from the image above that the ve
3 min read
Find vertex coordinates of all possible rectangles with a given vertex and dimensions
Given two integers L and B representing the length and breadth of a rectangle and a coordinate (X, Y) representing a point on the cartesian plane, the task is to find coordinates of all rectangles having a vertex as (X, Y) of the given dimensions. Example: Input: X=9, Y=9, L=5, B=3Output:(9, 9), (14, 9), (9, 12), (14, 12)(4, 9), (9, 9), (4, 12), (9
8 min read
Find all the Mother Vertices of a graph
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 belowOutput : 0 1 4 Explanation : In the given graph, the
13 min read
Area of a triangle with two vertices at midpoints of opposite sides of a square and the other vertex lying on vertex of a square
Given a positive integer N representing the side of a square, the task is to find the area of a triangle formed by connecting the midpoints of two adjacent sides and vertex opposite to the two sides. Examples: Input: N = 10Output: 37.5 Input: N = 1Output: 0.375 Approach: The given problem can be solved based on the following observations: The one s
5 min read
Maximum number of edges that N-vertex graph can have such that graph is Triangle free | Mantel's Theorem
Given a number N which is the number of nodes in a graph, the task is to find the maximum number of edges that N-vertex graph can have such that graph is triangle-free (which means there should not be any three edges A, B, C in the graph such that A is connected to B, B is connected to C and C is connected to A). The graph cannot contain a self-loo
4 min read
Find the Degree of a Particular vertex in a Graph
Given a graph G(V,E) as an adjacency matrix representation and a vertex, find the degree of the vertex v in the graph. Examples : 0-----1 |\ | | \ | | \| 2-----3 Input : ver = 0 Output : 3 Input : ver = 1 Output : 2 Algorithm: 1. Create the graphs adjacency matrix from src to des 2. For the given vertex then check if a path from this vertices to ot
7 min read
Article Tags :
Practice Tags :