Leetcode 261 Solution

This article provides solution to leetcode question 261 (graph-valid-tree)
Categories:
Tags:
Access this page by simply typing in "lcs 261" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/graph-valid-tree

Solution

class Solution {
public:
    int find(vector<int>& v, int i)
    {
        return i == v[i] ? i : v[i] = find(v, v[i]);
    }



    void merge(vector<int>& v, int a, int b)
    {
        int pa = find(v, a);
        int pb = find(v, b);
        v[pa] = pb;
    }



    bool validTree(int n, vector<pair<int, int>>& edges) {
        vector<int> v(n);
        for (int i = 0; i < n; i++)
            v[i] = i;



        if (edges.size() + 1 != n)
            return false;



        for (auto edge : edges)
        {
            if (find(v, edge.first) == find(v, edge.second))
                return false;



            merge(v, edge.first, edge.second);
        }



        return true;
    }
};