【lintcode】图是否是树

红太狼 2022-05-31 02:35 58阅读 0赞

给出 n 个节点，标号分别从 0 到 n - 1 并且给出一个 无向 边的列表 (给出每条边的两个顶点), 写一个函数去判断这张｀无向｀图是否是一棵树
    
    注意事项
    你可以假设我们不会给出重复的边在边的列表当中. 无向边　[0, 1] 和 [1, 0]　是同一条边， 因此他们不会同时出现在我们给你的边的列表当中。
    
    样例
    给出n = 5 并且 edges = [[0, 1], [0, 2], [0, 3], [1, 4]], 返回 true.
    给出n = 5 并且 edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], 返回 false.

思路：  
这是一个典型的并查集的问题，关于并查集原理见我的博文[并查集][Link 1]

代码实现

struct Set{
            int i;
            int rank;
            struct Set *p;
        };
    class Solution {
    public:
        /*
         * @param n: An integer
         * @param edges: a list of undirected edges
         * @return: true if it's a valid tree, or false
         */
        bool validTree(int n, vector<vector<int>> &edges) {
            // write your code here
            if(n == 0)
                return false;
            struct Set s[n];
    
            //将点集中的每个点都初始化为一个集合（树）
            for(int i = 0; i < n; i++){
                s[i].i = i;
                s[i].rank = 0;
                s[i].p = &s[i];
            }
    
            //若两个结点之间有边且分属于不相交的集合（树），则将它们所属的集合合并
            //若这两个结点属于相同的集合则说明它们所在的树中有环路
            for(int i = 0; i < edges.size(); i++){
                struct Set *x, *y;
                x = find_set(&s[edges[i][0]]);
                y = find_set(&s[edges[i][1]]);
                if(x != y) 
                    union_set(x, y);
                else
                    return false;
            }
    
            //若合并后的点集仍属于不同的树，则说明该图一个森林
            for(int i = 1; i < n; i++)
                if(find_set(&s[i]) != find_set(&s[0]))
                    return false;
    
            return true;
        }
    
        //按秩合并操作
        void union_set(struct Set *x, struct Set *y){
            if(x->rank < y->rank)
                x->p = y;
            else{
                y->p = x;
                if(x->rank == y->rank)
                    x->rank += 1;
            }
        }
    
        //带路径压缩的查找操作
        struct Set * find_set(struct Set *s){
            if(s->p != s)
                s->p = find_set(s->p);
            return s->p;
        }
    };

[Link 1]: http://blog.csdn.net/wait_nothing_alone/article/details/79254879