Algorithm
Problem link- https://www.spoj.com/problems/PT07Y/
PT07Y - Is it a tree
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
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <map>
using namespace std;
int main()
{
map <int , int >ma;
int n,m,ans=0,a,b;
scanf("%d",&n);
scanf("%d",&m);
if(m==n-1)
ans=1;
for(int i=0;i <m;i++)
{
scanf("%d",&a);
scanf("%d",&b);
if(ma.find(a)!=ma.end()&&ma.find(b)!=ma.end())
ans=0;
ma[a]=1;
ma[b]=1;
}
if(ans==1)
printf("YES\n");
else
printf("NO\n");
}Input
3 2
1 2
2 3
1 2
2 3
Output
YES
#2 Code Example with Java Programming
Code -
Java Programming
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;
class IsItATree {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String line = reader.readLine();
StringTokenizer st = new StringTokenizer(line, " ");
int v=Integer.parseInt(st.nextToken()), e=Integer.parseInt(st.nextToken());
/* Initialize adjacency list */
List<List<Integer>> adjacencyList = new ArrayList<List<Integer>>(v);
for (int i=0; i<v; i++){
adjacencyList.add(new LinkedList<Integer>());
}
/* Parse input to create adjacency list */
int tempEdges = e;
while(tempEdges-- > 0){
line = reader.readLine();
st = new StringTokenizer(line, " ");
int e1= Integer.parseInt(st.nextToken()), e2= Integer.parseInt(st.nextToken());
adjacencyList.get(e1-1).add(e2-1);
}
/* Initialize a stack for Depth First Search */
Stack<Integer> stack = new Stack<>();
stack.push(0);
/* boolean array to keep track of visited nodes */
boolean[] visited = new boolean[v];
int nodesVisited = 0;
while(!stack.isEmpty()){
Integer top = stack.pop();
stack.addAll(adjacencyList.get(top));
/* if already discovered node is visited again, it's a loop.
* So it can't be a tree.
*
* If not then mark the node as visited and increase count
* of visited nodes.
* */
if (visited[top]){
break;
} else {
visited[top] = true;
nodesVisited++;
}
}
/* if stack is not empty(loop was broken before full DFS, line 51)
* or all the nodes are not visited, then this is not a tree;
* else it is a tree.
* */
System.out.println(!stack.isEmpty() || nodesVisited != v ? "NO" : "YES");
}
}Input
3 2
1 2
2 3
1 2
2 3
Output
YES
Demonstration
SPOJ Solution-PT07Y Is it a tree-Solution in C, C++, Java, Python,SPOJ Solution