Given a directed graph, check if the incoming edges of a vertex is equal to the vertex itself.

Problem Statement:

You are given a directed graph, you need to check if the incoming edges of a vertex is equal to the vertex itself.

Example

The above graph should return true.

Solution

So the solution is to traverse the adjacency list for all the vertices.

Then increment the count of edges of every vertex that has an incoming edge from i.

Do this step for every vertex and check the degree of all the vertex is equal or not.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 
#include <list> 

using namespace std;

class Graph
{

private:
   int V; 
   list<int> *adj; // to hold adjacency list
public:
   Graph(int V); // Constructor
   void add_edge(int v, int w); // to add an edge to graph
   void print_graph();
   bool count_indegree();
};

Graph::Graph(int V)
{
   // get the total number of nodes
   this->V = V;

   // initialize adjacency list for that number of nodes
   adj = new list<int>[V];
}

void Graph::add_edge(int v, int w)
{
   // add the edge to adjacency list
   adj[v].push_back(w); 
}

void Graph::print_graph()
{
   for(auto i = 0; i < V; i++)
   {
      cout<<"\nAdjacency list of vertex "<<i<<endl;

      for(auto j = adj[i].begin(); j != adj[i].end(); j++)
      {
         cout<<" ->"<<*j;
      }
   }
}

bool Graph::count_indegree()
{
   int in_degree[10] = {0};

   for(int i = 0; i < V; i++)
   {
      for(auto j = adj[i].begin(); j != adj[i].end(); j++)
      {
         int edge = *j;
         in_degree[edge]++;
      }
   }

   for (int i = 0; i < V; i++) {
      if (i == in_degree[i])
         continue;
      else
         return false;
   }
   return true;

}

int main()
{

   Graph g(4);
   g.add_edge(0, 1);
   g.add_edge(1, 2);
   g.add_edge(0, 2);
   g.add_edge(0, 3);
   g.add_edge(1, 3);
   g.add_edge(2, 3);


   if(g.count_indegree()){
      cout<<"True"<<endl;
   } else {
      cout<<"False"<<endl;
   }

   return 0;
}

Output:

True