I asked the user to enter adjacency matrix and i tried to check by the following code, but sometimes it gives me "Graph is not a tree" whatever the input was and sometimes it turns to an infinite loop and shows "enter number of nodes" forever
What I have tried:
#include <iostream>
#include <stdlib.h>
using namespace std;
int v;
bool isCycle(int u, bool visited[], int parent) {
int **A;
cout<< "Enter number of nodes \n";
cin>>v;
A=(int**)malloc(v*sizeof(int*));
if(A==NULL)
{
cout<<"Out of memory";
return 1;
}
for(int i=0;i<v;i++)
{
A[i]=(int*)malloc(v*sizeof(int));
if(A[i]==NULL)
{
cout<<"Out of memory";
return 1;
}
}
cout<<"NOTE that your Adjacency Matrix contains ZEROs and ONEs ONLY \n";
cout<<"Enter your Adjacency Matrix \n";
for(int i=0;i<v;i++) {
for(int j=0;j<v;j++)
{
cin>>A[i][j];
}
}
visited[u] = true; for(int b = 0; b<v; b++) {
if(A[u][b]) {
if(!visited[b]) { if(isCycle(b, visited, u)) {
return true;
}
} else if(b != parent) { return true; }
}
}
return false;
}
bool isTree() {
bool *vis = new bool[v];
for(int i = 0; i<v; i++)
vis[i] = false;
if(isCycle(0, vis, -1)) return false;
for(int i = 0; i<v; i++) {
if(!vis[i]) return false;
}
return true;
}
int main() {
if(isTree())
cout << "The Graph is a Tree.";
else
cout << "The Graph is not a Tree.";
}