Last Updated: 29 Jul, 2020
Is It A Tree?
Moderate
Asked in companies
Given a graph with 'V' vertices numbered from 0 to 'V' - 1 and 'E' edges. Determine if it is a tree or not?
Input Format :
The first line of input contains two integers 'E' and 'V', separated by a single space. They denote the total number of edges and vertices respectively.
From the second line onwards, the next 'V' lines represent an edge between the two vertices.
Every edge is represented by two vertices(u, v) that share an edge between them. The values of the vertices would again be separated by a single space.
Output Format :
The only line of output prints 'True' if the given graph is a tree, otherwise print 'False'.
Constraints :
1 < 'V' <= 10^5
0 <= 'E' <= min(10^5, V*(V-1)/2)
0 <= u, v <= V-1
Time Limit: 1 sec
Approaches
A graph is a tree if the following two conditions are satisfied:
- There are no cycles present in the graph
- The graph is connected
Algorithm for checking cycle in Graph.
- Create the graph using the given number of edges and vertices.
- Run a DFS from starting from any vertex along with the track of the parent (initially, parent of every vertex is -1)
- Recur for all the vertices adjacent to the current vertex.
- If an adjacent vertex is not visited, then recur for that adjacent vertex.
- If an adjacent vertex is visited and it is not the parent of the current vertex, then there is a cycle.
Algorithm for checking whether the graph is connected or not
1. After DFS, check if all the vertex is not visited or not.
2. If it is visited then it is connected.
A graph is a tree if the following two conditions are satisfied:
- There are no cycles present in the graph
- The graph is connected
Algorithm for checking cycle in Graph.
- Create the graph using the given number of edges and vertices.
- Run a BFS from starting from any vertex along with the track of the parent.
- Push vertex into queue and mark its parent as -1.
- Run a loop while the queue is not empty.
- Dequeue vertex from queue and add all its unvisited adjacent to queue and mark it visited.
- For vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in the graph.
Algorithm for checking whether the graph is connected or not
- After BFS, check if all the vertex is not visited or not.
- If all the vertices are visited then it is connected.