algorithm - 如何判断一个图是否是树？

Question

我正在尝试解决 SPOJ 问题 is it a tree ?我必须在其中检查图形是否为树？？在这个问题中，我使用 DFS 来检测图形是否有循环..

我的代码是..

#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;
}

当我提交解决方案时，我收到了“超出时间限制”的消息。有没有更好的方法来解决这个问题？？

Answer 1

正如 kevmo314 在他的评论中提到的，我们需要检查图的连通性和边数是否恰好为 n-1，以确保图是树。

所以有两个观察结果:

• 如果边数为 n - 1，我们只需要检查连通性。

• 使用 disjoint set对于这个问题，作为每一条边，如果它是一棵树，那么这条边应该连接两个不连通的分量，否则，这个图就不是树。所以时间复杂度为 O(n)，因为只有 n - 1 条边需要检查。