graph valid tree

solution

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

利用并查集判断一个edge的左边和右边是否在一个set中,是的话Return false。

http://www.lintcode.com/en/problem/graph-valid-tree/

code


class unionfind {
public:
    map<int, int> hash;

    unionfind(int n)
    {
        for(int i = 0; i<n; i++)
        {
            hash[i] = i;
        }
    }

    int find(int key)
    {
        while(key != hash[key])
        {
            key = hash[key];
        }

        return key;
    }

    int ufind(int key)
    {
        int boss = find(key);
        while(key != boss)
        {
            key = hash[key];
            hash[key] = boss;
        }

        return boss;
    }

    bool unionboss(int a, int b)
    {
        int bossa = ufind(a);
        int bossb = ufind(b);

        if(bossa == bossb)
        {
            return false;
        }
        else
        {
            hash[bossa] = bossb;
            return true;
        }
    }
};

class Solution {
public:

    bool validTree(int n, vector<pair<int, int>>& edges) {
        int size = edges.size();
        if(n == 1 && size == 0)
        {
            return true;
        }

        if(size == 0)
        {
            return false;
        }

        unionfind uf(n);

        for(pair<int, int> p : edges)
        {
            if(uf.unionboss(p.first, p.second) == false)
            {
                return false;
            }
        }

        int boss = uf.ufind(0);
        for(int i = 1; i<n; i++)
        {
            if(uf.ufind(i) != boss)
            {
                return false;
            }
        }

        return true;
    }
};

code

class UnionFind {
public:

    map<int, int> hash;

    void addNode(int key, int val)
    {
        hash[key] = val;
    }

    int find(int key)
    {
        while(key != hash[key])
        {
            key = hash[key];
        }

        return key;
    }

    int compress_find(int key)
    {
        int boss = find(key);
        while(key != boss)
        {
            int next = hash[key];
            hash[key] = boss;
            key = next;
        }

        return boss;
    }

    void bossunion(int key1, int key2)
    {
        int boss1 = compress_find(key1);
        int boss2 = compress_find(key2);

        if(boss1 != boss2)
        {
            hash[boss1] = boss2;
        }
    }
};

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(edges.size() == 0)
        {
            if(n == 1)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        UnionFind uf;

        for(vector<int> tmp : edges)
        {
            int left = tmp[0];
            int right = tmp[1];

            if(uf.hash.find(left) == uf.hash.end())
            {
                uf.addNode(left, left);
            }

            if(uf.hash.find(right) == uf.hash.end())
            {
                uf.addNode(right, right);
            }

            if(uf.compress_find(left) == uf.compress_find(right))
            {
                return false;
            }
            else
            {
                uf.bossunion(left, right);
            }
        }

        if(uf.hash.size() != n)
        {
            return false;
        }

        return true;
    }
};

results matching ""

    No results matching ""