# Program to check if the given graph is a tree or not | faceprep

Program to check if the given graph is a tree or not is discussed here.

An undirected graph is given as input,

The given graph is said to be a tree,

• The graph is connected.
• When there are no cycles in the graph.

For example, The above-given graph is not a tree because it has a cycle. ## Algorithm to check if the given graph is a tree or not

• Input the graph.
• Check if the graph has any cycles in it.
• If it has a cycle, then print “The given graph is not a tree”.
• Else, print “The given graph is a tree”.

Program to check if the given graph is a tree or not is given below.

// C++ Program to check whether a graph is a tree or not
#include<iostream>
#include <list>
#include <limits.h>
using namespace std;

// Class representation for an undirected graph
class Graph
{
int V;
bool cycle_presence(int v, bool visited[], int parent);
public:
Graph(int V);
void add_edge_graph(int v, int w); // Add an edge to the graph
bool isTree(); // Returns true if graph is tree
};

int main()
{
Graph graph1(5);
char ch;
int a, b;
cout << “\nEnter the connections of graph 1\n”;
do
{
cin >> a >> b >> ch;
}while(ch == ‘y’ || ch == ‘Y’);

graph1.isTree()? cout << “The given graph is a tree\n”: cout << “The given graph is not a tree\n”;
Graph graph2(5);
cout << “\nEnter the connections of graph 2\n”;
do
{
cin >> a >> b >> ch;
}while(ch == ‘y’ || ch == ‘Y’);

graph2.isTree()? cout << “The given graph is a tree\n”: cout << “The given graph is not a tree\n”;

return 0;
}

Graph::Graph(int V)
{
this->V = V;
}

// Adding the edges to the graph
{
}

// Function that uses visited[] and parent to detect cycle
bool Graph::cycle_presence(int v, bool visited[], int parent)
{
// Mark current node as visited
visited[v] = true;

// Recur for all the vertexes adjacent to this vertex
list<int>::iterator i;
{

if (!visited[*i])
{
if (cycle_presence(*i, visited, v))
return true;
}

// If an adjacent is visited and not parent of current vertex, then there is a cycle.
else if (*i != parent)
return true;
}
return false;
}

// Returns true if the graph is a tree, else returns false.
bool Graph::isTree()
{
// Mark all the vertexes as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;

if (cycle_presence(0, visited, -1))
return false;

for (int u = 0; u < V; u++)
if (!visited[u])
return false;

return true;
}

Output: 