7678-树tree

根据树的定义，判断一个连通图是不是树有两种方法：

• 节点数=边数+1
• 有没有环
  判断环的方式比较简单。
  方法1：除了父节点，遇到的点如果已经被访问过了，说明存在环，也就是说不是树。
  可以用一个全局变量记录有没有遇到以及访问过的节点。

void dfs(int x, int fa)
{
    vis[x] = 1;
    for(auto y : G[x]){
        if(y!=fa){
            if(vis[y]) {
               tag = 1;   //遇到了环，那么不是树
               return;
            }
            dfs(y,x);
        }
    }
}
 

方法2：
遇到访问过的节点或返回值为$1$，则表示不是树。（$1$不是树，$0$为树）

bool dfs(int x, int fa)
{
    vis[x] = 1;
    for(auto y : G[x]){
        if(y!=fa){
            if(vis[y] || dfs(y,x)) return 1;
        }
    }
    return 0;  //没有中途返回，那说明是棵树
}