I have faced this question in Amazon online test.....
You are given an unweighted, undirected graph. Write a program to check if it's a tree topology.
Input
The first line of the input file contains two integers N and M --- number of nodes and number of edges in the graph (0 < N <= 10000, 0 <= M <= 20000). Next M lines contain M edges of that graph --- Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u,v <= N).
Output
Print YES if the given graph is a tree, otherwise print NO.
Example
Input:
3 2
1 2
2 3
Output:
YES
Solution:-Things to consider:-
a) Whether there is cycle or not.
b) Whether there is any connected component exist or not.
General solution Hints:-
Create an Adjacency List/Matrix and maintain an Vector to check out the back edges of the graph if it found return 0, it means it is creating a cycle so it can't be tree. Second thing to consider is whether there is component or not if there is component exist in this case too it can't be tree.
Best Solutions:- Surprisingly solution is very easy if you think hard.
a)First condition can be checked by vertices==edges+1 to be tree.
2)Connected component can be checked by using sets. All edges should be in a single set to be a tree
#include<iostream>
#include<cstdlib>
using namespace std;
void Makeset(int Set[],int N)
{
for(int i=0;i<=N;i++)
Set[i]=-1;
}
int Find(int Set[],int size)
{
if(Set[size]<0)
return size;
return Find(Set,Set[size]);
}
bool Union(int Set[],int N)
{
int u,v,c;
for(int i=0;i<N;i++)
{
cin>>u>>v;
--u,--v; //Because values ranges from 1 to n and we have array 0 to n-1 ;)
u=Find(Set,u);
v=Find(Set,v);
if(u==v)
return false; // if making cycle
else if(Set[u]>Set[v])
{
c=Set[u];
Set[u]=v;
Set[v]+=c;
}
else if(Set[u]<Set[v])
{
c=Set[v];
Set[v]=u;
Set[u]+=c;
}
else
{
c=Set[v];
Set[v]=u;
Set[u]+=c;
}
}
return true;
}
int main()
{ int *Set=NULL;
int N,M;
bool f=false;
cin>>M>>N;
if(M==N+1)
{
Set=new int[M];
Makeset(Set,N);
f=Union(Set,N);
}
if(f)
cout<<"YES";
else
cout<<"NO";
return 0;
}
My solution using Adjacency list goes like this... Don't forget to check out my Adjacency Matrix solution below
#include<iostream>
using namespace std;
struct Adlist
{
int data;
Adlist *next;
};
struct Graph
{
int V;
int E;
Adlist *list;
};
void Create_Graph(Graph *G)
{
int u,v;
Adlist *ptr=NULL;
for(int i=0;i<G->E;i++)
{ Adlist *node=new Adlist;
cin>>u>>v;
u=u-1;
v=v-1;
node->data=v;
node->next=NULL;
if(G->list[u].next==NULL)
G->list[u].next=node;
else
{ptr=G->list[u].next;
while(ptr->next)
ptr=ptr->next;
ptr->next=node;
}
Adlist *node1=new Adlist;
node1->data=u;
node1->next=NULL;
if(G->list[v].next==NULL)
G->list[v].next=node1;
else
{
ptr=G->list[v].next;
while(ptr->next)
ptr=ptr->next;
ptr->next=node1;
}
}
}
void DFS(Graph *G,int u,char *Visited)
{
if(Visited[u]==49)
return;
Visited[u]=49;
for(int v=0;v<G->V;v++)
{
DFS(G,v,Visited);
}
}
int main(void)
{ int k=1;
Graph *G=new Graph;
if(!G)return 0;
cin>>G->V>>G->E;
G->list=new Adlist[G->V];
if(!G->list)return 0;
char *Visited=new char[G->V];
for(int v=0;v<G->V;v++)
{
G->list[v].data=0;
G->list[v].next=NULL;
Visited[v]=48;
}
Create_Graph(G);
DFS(G,0,Visited);
for(int i=0;i<G->V;i++)
if(Visited[i]!=49)
{
k=0;break;
}
if(G->V==G->E+1&&k)
cout<<"YES";
else
cout<<"NO";
}
//By using Adjacency Matrix
#include<iostream>
#include<cstdlib>
using namespace std;
struct Graph
{
int V;
int E;
int **Matrix;
};
Graph *Create(Graph *G)
{
int u,v;
G->Matrix=new int*[G->V];
for(int i=0;i<G->V;i++)
G->Matrix[i]=new int[G->V];
for(int i=0;i<G->E;i++)
{
cin>>u>>v;
G->Matrix[u-1][v-1]=1;
G->Matrix[v-1][u-1]=1;
}
return G;
}
int DFS(Graph *G,int u,int *Visited)
{
if(Visited[u]!=-1)
return 0;
Visited[u]=1;
for(int v=0;v<G->V;v++)
{
if(G->Matrix[u][v])
DFS(G,v,Visited);
}
return 1;
}
int main(void)
{ int *Visited=NULL;
Graph *G=new Graph;
cin>>G->V>>G->E;
G->Matrix=NULL;
G=Create(G);
Visited=new int[G->V];
for(int i=0;i<G->V;i++)
Visited[i]=-1;
int k=DFS(G,0,Visited);
if(k==0)
cout<<"NO";
else
{
for(int v=0;v<G->V;v++)
{
if(Visited[v]==-1)
{cout<<"NO"; return 0;}
}
cout<<"YES";
}
}
