261. Graph Valid Tree - cocoder39/coco39_LC GitHub Wiki

261. Graph Valid Tree

Notes 2020:

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        graph = {}
        for i in range(n):
            graph[i] = []
        
        for x, y in edges:
            graph[x].append(y)
            graph[y].append(x)
        
        queue = collections.deque([0])
        visited = set([0])
        parent = {}
        while queue:
            sz = len(queue)
            for i in range(sz):
                cur_node = queue.pop()
                for next_node in graph[cur_node]:
                    if cur_node in parent and next_node == parent[cur_node]:
                        continue
                    if next_node in visited:
                        return False
                    visited.add(next_node)
                    parent[next_node] = cur_node
                    queue.append(next_node)
        
        return len(visited) == n

============================================================================================================

According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. Two points: 1 any two vertices are connected, 2 no cycle

we can use union find to solve this problem. if there is only one unite exists, then all vertices are connected. If both ends of an edge are already in the same unite, then there is cycle.

class Solution {
public:
    bool validTree(int n, vector<pair<int, int>>& edges) {
        UnionFind uf(n); // O(n)
        for (auto edge : edges) { //O(|v|)
            if (uf.isConnected(edge.first, edge.second)) //O(lg* n)
                return false;
            uf.makeUnion(edge.first, edge.second); //O(lg* n)
        }
        return uf.getCnt() == 1;
    }
private:
    class UnionFind {
        public:
            UnionFind(int n) {
                cnt = n;
                for (int i = 0; i < n; i++) {
                    id.push_back(i);
                    sz.push_back(1);
                }
            }
        
            bool isConnected(int p, int q) {
                return root(p) == root(q);
            }
            
            void makeUnion(int p, int q) {
                int i = id[p];
                int j = id[q];
                if (i == j) return;
                
                if (sz[i] < sz[j]) {
                    id[i] = j;
                    sz[j] += sz[i];
                }
                else {
                    id[j] = i;
                    sz[i] += sz[j];
                }
                cnt--;
            }
            
            int getCnt() {
                return cnt;
            }
            
        private:
            vector<int> id;
            vector<int> sz;
            int cnt;
            
            int root(int i) {
                while (i != id[i]) {
                    id[i] = id[id[i]];
                    i = id[i];
                }
                return i;
            }
    };
};

dfs

class Solution {
public:
    bool validTree(int n, vector<pair<int, int>>& edges) {
        unordered_map<int, vector<int>> graph;
        for (auto edge : edges) {
            graph[edge.first].push_back(edge.second);
            graph[edge.second].push_back(edge.first);
        }
        
        unordered_set<int> visited;
        if (!dfs(graph, visited, 0, -1))    return false;
        return visited.size() == n;
    }
private:
    bool dfs(unordered_map<int, vector<int>>& graph, unordered_set<int>& visited, int cur, int pre) {
        visited.insert(cur);
        for (auto neighbor : graph[cur]) {
            if (neighbor == pre)    continue;
            if (visited.find(neighbor) != visited.end())    return false;
            if (!dfs(graph, visited, neighbor, cur))    return false;
        }
        return true;
    }
};

bfs

bool validTree(int n, vector<pair<int, int>>& edges) {
        unordered_map<int, vector<int>> graph;
        for (auto edge : edges) {
            graph[edge.first].push_back(edge.second);
            graph[edge.second].push_back(edge.first);
        }
        
        vector<int> parent(n, -1);
        queue<int> qu;
        qu.push(0);
        parent[0] = 0;
        while (! qu.empty()) {
            int cur = qu.front();
            qu.pop();
            
            for (auto neighbor : graph[cur]) {
                if (neighbor == parent[cur])    continue;
                if (parent[neighbor] != -1)     return false;
                parent[neighbor] = cur;
                qu.push(neighbor);
            }
        }
        
        for (auto p : parent) {
            if (p == -1)    return false;
        }
        return true;
    }
⚠️ **GitHub.com Fallback** ⚠️