以图判树（并查集）_给定编号从0到n-1的n个节点,给定一个整数n和一个edges列表

题目描述：

给定编号从 0 到 n - 1 的 n 个结点。给定一个整数 n 和一个 edges 列表，其中 edges[i] = [ai, bi] 表示图中节点 ai 和 bi 之间存在一条无向边。

如果这些边能够形成一个合法有效的树结构，则返回 true ，否则返回 false 。

实例：

输入: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
输出: true

思路：

        对于小合集合并为大合集的题目首先就要想到并查集。

        例如：已知两两亲戚关系，求A、B是否为亲属等问题。

        例如：已知结点边的集合，求是否构成单棵树。

并查集思路：

        1. 查找函数（find）：

                对于某节点A，若A的前驱不等于本身，则让A=A.pre，并循环。

                直到找到一个节点，其前驱等于其本身。则此节点为先前A节点的根节点，返回该节点

        2. 合并函数（merge）：

                对于A和B两个子树的根节点，判断其树高（or 树大小），小树合并到大树内。

                即：判断根节点A、B的size，若A.size<B.size，将A的前驱赋值为B。

        3.判断依据：

                若并查集之后，对于任意两个节点A、B，若A的根节点和B的根节点是同一个，则说明在同一个集合之中。

                对于上诉提到的亲戚案例，可以理解为：祖父相同，有血缘关系。

                对于以图判树题目，可以理解为：

                        ①若在合并过程中，处理新纪录时出现根节点一致的情况，说明有环，直接返回false

                        ②若在合并完成之后（说明已经无环），如果合并次数<节点数-1，说明无法构成一颗树，（即：有多个树存在），也需要返回false

                        ③若①、②都正常，则是一个正常的树，返回true。

        注意事项：

                对于用结构体树的写法，需要注意的是，find返回的并不是真正的很节点本身，而是根节点的拷贝。对于拷贝不能直接merge而是需要先找到真正的根节点再merge。

代码示例：        

class Solution {
private:
    int N;
    struct TreeNode{
        int data;
        int size;
        TreeNode * pre;
    };
public:
    TreeNode find(TreeNode &node){
        TreeNode temp=node;
        while(temp.pre->data != temp.data){
            temp=*temp.pre;
        }
        //cout<<"temp"<<temp.data<<'\n';
        return temp;
    }
    int merge(TreeNode &node1,TreeNode &node2){
        if(node1.size>=node2.size){
            node1.pre = &node2;
            node2.size+=node1.size;
        }
        else{
            node2.pre = &node1;
            node1.size+=node2.size;
        }
        N--;
        return 0;
    }
    bool validTree(int n, vector<vector<int>>& edges) {
        N=n;
        TreeNode Node[n];
        for(int i=0;i<n;i++){
            Node[i].data=i;
            Node[i].pre = &Node[i];
            Node[i].size=1;
        }
 
        for(int i=0;i<edges.size();i++){
            TreeNode Node1 = find(Node[edges[i][0]]);
            TreeNode Node2 = find(Node[edges[i][1]]);
 
            cout<<"i="<<i<<' '<<Node1.data<<' '<<Node2.data<<'\n';
            if(Node1.data!=Node2.data){
                merge(Node[Node1.data],Node[Node2.data]);
                cout<<"merge="<<Node[Node1.data].pre->data<<' '<<Node[Node2.data].pre->data<<'\n';
                cout<<'\n';
            }
            else{
                cout<<"here1";
                return false;
            } 
        }
        cout<<"here2="<<N;
        if(N==1) return true;
        else return false;
 
    }
};