Simple and clean c++ solution, with detailed explanation.


  • 95
    X
    class Solution {
    public:
        bool validTree(int n, vector<pair<int, int>>& edges) {
            vector<int> nodes(n,0);
            for(int i=0; i<n; i++) nodes[i] = i;
            for(int i=0; i<edges.size(); i++){
                int f = edges[i].first;
                int s = edges[i].second;
                while(nodes[f]!=f) f = nodes[f];
                while(nodes[s]!=s) s = nodes[s];
                if(nodes[f] == nodes[s]) return false;
                nodes[s] = f;
            }
            return edges.size() == n-1;
        }
    };
    

    To tell whether a graph is a valid tree, we have to:

    1. Make sure there is no cycle in the graph - this has to be a none-cyclic graph;
    2. Make sure every node is reached - this has to be a connected graph;

    Reference: https://en.wikipedia.org/wiki/Tree_(graph_theory)

    Solution:

    1. To test cyclic, we can make an array for each node (as array index), and the array will store the parent of the node (as array index). Every time we fetch a new pair of nodes, we trace the root node (the deepest parent node) of these two nodes, if it has the same root, then is will be a cycle; otherwise, we set the parent of second node to be the first node;
    2. After we make sure there is node cycle in the graph, we simple test if there is enough edges to make this graph connected.

  • 2
    G

    Great solution and explanation, should have more upvotes


  • 5
    Z

    You probably want to mark it as union find problem. It is smart to use the number of edge to tell whether they are from one tree once you are sure there is no cycle.


  • 0
    H

    The best union find solution! It beats 99% other submissions and deserves more up-votes!


  • 5
    S

    I think you can check the edge.size() == n - 1 at the beginning of the code to save more time.


  • 1
    D

    I think it can be faster if using compatization by adding nodes[f] = nodes[nodes[f]]; // and similar for s in the root searching loops.


  • 0
    O

    @ducalpha

    Agree, but maybe you are referring to path compression


  • 0
    F

    @ducalpha Totally agree. Kind of path compression trick.


  • 0
    F

    @ducalpha
    I tried put compression in but the speed isn't faster. Even though I believe compression can faster.


  • 2
    D

    @fakewen The test cases on leetcode seems quite small and not large enough to show the advantages of the compression.


  • 0

    Brilliant idea!! you just need to check
    if(s == f)
    instead of if(nodes[s] == nodes[f]) actually,


  • 0
    M

    How about the case [[0,1] , [0,2] , [1,2] , [3,4]] ? Here we have 5 nodes and 4 edges in which using your logic it would be enough to make a connected graph, but this example is not connected.

    I believe your logic handles this case however, because the only way we can have this case is if we have a cycle, in which you check for this first so it would get eliminated there.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.