PT07Y - Is it a tree Problem Editorial Spoj (OR) Graph is Tree or not Verification Problem - UCS - Unleash-Coding-Skills

Tuesday, 27 March 2018

PT07Y - Is it a tree Problem Editorial Spoj (OR) Graph is Tree or not Verification Problem - UCS

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

Problem link:

http://www.spoj.com/problems/PT07Y/


For Solving this problem we use a stack and dfs iterative approach.First Look at once at DFS iterative approach and how it proceeds.

DFS-iterative (G, s):                                   //Where G is graph and s is source vertex
      let S be stack
      S.push( s )            //Inserting s in stack 
      mark s as visited.
      while ( S is not empty):
          //Pop a vertex from stack to visit next
          v  =  S.top( )
         S.pop( )
         //Push all the neighbours of v in stack that are not visited   
        for all neighbours w of v in Graph G:
            if w is not visited :
                     S.push( w )         
                    mark w as visited
 
 
In this first G is Graph and s is  starting vertex which is inserted in to stack and we will insert all the non visited adjacent vertices  of the top vertex in stack and the process continues till end of stack.This is our DFS iterative method.

Now come to our problem.In the same manner like DFS iterative we will insert initially a starting vertex in to stack and process continues by inserting all vertices that has path from it to current stack top element which is represented by v[j][i] in inner for loop of the solution below.Unlike DFS we mark the vertex as visited only when it comes to top of stack position before poping in the loop as show in code below.

First Condition:

In this process of adding elements in to stack if encounter a stack top element which is already visited means there encountered a vertex which is already been visited and now we can know that it is not representing a tree ,it is now representing a graph.

Now you got a doubt what is difference between tree and graph.You are thinking correct.....

Tree: Tree is special form of graph i.e. minimally connected graph and having only one path between any two vertices.

Graph:In graph there can be more than one path i.e. graph can have uni-directional or bi-directional paths (edges) between nodes

We are representing return "0" in program if it is not a tree.Otherwise, we return "1" if it a tree.

After Stack becomes empty we need to check again second condition.

Second Condition:

Is all vertices in the given input are visited or not.If all the vertices are not visited then it doesn't represent a tree.

For this condition we have placed logic in our solution as:

if(ko==n)
   return 1;
   else
   return 0;
means if we have visited all vertices ko will equal to n and it will be a valid tree.
otherwise return "0" for invalid tree.
In this solution we have taken a visit array to know whether we have visited a vertex or not initially all of them are set to false or 0

The complete solution for this problem is:

#include <iostream>
#include <stack>
#include <cstdio>
#include <vector>
using namespace std;
int ko;
int n,m;
    vector<int>v[10001];
int  dfs()
{
    int i,j,k;
    stack<int>s;
    bool visit[10010];
    for(i=1;i<=n;i++)
    {
        visit[i]=0;
    }
    s.push(1);
    ko=0;

    while(s.size()>0)
    {
        ko++;
        j=s.top();
        s.pop();
        if(visit[j]==true)
        {
     return 0;
        }
        visit[j]=true;
        for(i=0;i<v[j].size();i++)
        {
         s.push(v[j][i]);   
        }
    }
  
if(ko==n)
   return 1;
   else
   return 0;
}
int main() {
    int i,j,k,io,ko;
scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
     scanf("%d %d",&j,&k);
        v[j].push_back(k);
    }
k=    dfs();
    if(k==1&&(m+1==n))
    printf("YES\n");
    else
printf("NO\n");
    return 0;
}


Happy Coding...

Feel Free to ask queries in comment section.........

No comments:

Post a comment