Graph Valid Tree

• Lintcode : 178 / Leetcode : 261
• Level : Medium

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

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

Input: n = 5 edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output: false.
Notice
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.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n)
space: O(n)

Answer

class Solution {
public:
    bool validTree(int n, vector<vector<int>> &edges) {
        // 判斷是否為tree 
        /*
            1. cycle
            2. edges = nodes - 1
        */
        map<int, unordered_set<int>> g;
        unordered_set<int> nodes;
        queue<int> q;
        // 因為不確定哪個會是parent
        // ex: 不一定是 [[0, 1]]，可能是[[1, 0]]
        for (auto it : edges) {
            g[it[0]].insert(it[1]);
            g[it[1]].insert(it[0]);
        }
        q.push(0);
        nodes.insert(0);
        while (!q.empty()) {
            int node = q.front(); q.pop();
            for (auto a : g[node]) {
                // 有重複代表有cycle
                if (nodes.find(a) != nodes.end()) return false;
                q.push(a);
                nodes.insert(a);
                g[a].erase(node);
            }
        }
        // 避免 n 很多，但是沒有全部都拿來建構樹
        // ex: n = 3, edges = [[0, 1]]
        return nodes.size() == n;
    }
};

tags: BFS

​