261. Graph Valid Tree

• Difficulty: Medium

• Topics: Depth-first Search, Breadth-first Search, Union Find, Graph

• Similar Questions:

  • Course Schedule

  • Number of Connected Components in an Undirected Graph

Problem:

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 1:

Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true

Example 2:

Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: false

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0,1] is the same as [1,0] and thus will not appear together in edges.

Solutions:

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph (n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        int edgeNum = edges.size();

        if (edgeNum != n - 1)   return false;
        vector<bool> visited(n, false);
        int nodeCount = getConnectedNode(0, graph, visited);
        return nodeCount == n;
    }

    int getConnectedNode(int start, vector<vector<int>>& graph, vector<bool>& visited) {
        if (visited[start]) return 0;
        int count = 1;
        visited[start] = true;
        for (auto& neighbor : graph[start]) {
            count += getConnectedNode(neighbor, graph, visited);
        }

        return count;
    }
};