Q:

how to find whether a graph is tree or not?

i am trying to solve a SPOJ problem is it a tree ? in which i have to check whether a graph is tree or not??
in this problem i am using DFS to detect whether the graph has cycle or not..
my code is..
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <string.h>

using namespace std;

typedef long long int64;
typedef unsigned long long uint64;
#define two(X) (1<<(X))
#define twoL(X) (((int64)(1))<<(X))
#define contain(S,X) (((S)&two(X))!=0)
#define containL(S,X) (((S)&twoL(X))!=0)
const double pi=acos(-1.0);
const double eps=1e-11;
template<class T> inline void checkmin(T &a,T b){if(b<a) a=b;}
template<class T> inline void checkmax(T &a,T b){if(b>a) a=b;}
template<class T> inline T sqr(T x){return x*x;}
typedef pair<int,int> ipair;
#define SIZE(A) ((int)A.size())
#define LENGTH(A) ((int)A.length())
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
int scanInt()
{
    char c;
    int ans=0;
    while(true)
    {
        c=getchar_unlocked();
        if(c==' ' || c=='\n')
            return ans;
        ans=(ans<<3)+(ans<<1)+c-'0';
    }
}
bool applyDFS(vector<vector<int> > &graph,int n)
{
    queue <int> st;
    int i,j=0;
    vector<bool> visited(n+1,false);
    int node=1;
    st.push(1);
    while(!st.empty())
    {
        node=st.front();
        st.pop();
        if(visited[node])
           {
            return false;
            }
            visited[node]=true;
        for(i=0;i<graph[node].size();i++)
            {
                if(!visited[graph[node][i]])
                    st.push(graph[node][i]);
            }
        j++;
    }
    return j==n?true:false;
}
int main()
{
    int n,m,x,y,i;
    //freopen("input.txt","r",stdin);
    n=scanInt();
    m=scanInt();
       vector <vector<int> > graph(n+1);
       stack <int > st;
    for(i=0;i<m;i++)
    {
          x=scanInt();
          y=scanInt();
          graph[x].PB(y);
          graph[y].PB(x);
          st.push(x);
    }
    if(applyDFS(graph,n))
        cout<<"YES\n";
    else
        cout<<"NO\n";
    return 0;
}

when i submit the solution i got a "time limit exceeded" message. Is there any better approach to solve this problem??

A:

As mention by  kevmo314 in his comment, we need to check for both connectivity of the graph and the number of edges are exactly n-1 to make sure that the graph is a tree.
So there are two observations: 

We only need to check for connectivity if the number of edges is n - 1.
Use disjoint set for this problem, as every edge, if it is a tree, this edge should connect two disconnected components, otherwise, this graph is not a tree. So time complexity is O(n) as there are only n - 1 edge to check.

