C++ solution, DFS


  • 3
    L
       class Gragh {
    public:
        int v_nums;  // number of nodes
        int e_nums;  // number of edges
        bool isCycle;
        vector<vector<int>> adjs;    // edges;
        vector<int> color; // color for all the node; 0 no visited, 1 during visited, 2, finished visited
        void addEdge(int v, int u) {
            adjs[v].push_back(u);
            adjs[u].push_back(v);
        }
        Gragh(int nums) : v_nums(nums), isCycle(false), adjs(vector<vector<int>>(v_nums, vector<int>())),
                color(vector<int>(v_nums)) {}
        
        bool isTreeGragh(){
            vector<int> res;
            int first_node = -1;
            for (int i = 0; i < v_nums; i++) {
                if (!adjs[i].empty()) {first_node = i; break;}
            }
            if (first_node == -1) return v_nums <= 1;
            dfs(first_node, -1, res);
            return !isCycle && res.size() == v_nums;
        }
    private:
        bool dfs(int node, int parent, vector<int> &res) {
            if (color[node] == 1) {isCycle = true; return true;}
            res.push_back(node);
            cout << " node in dfs " << node << endl;
            for (auto v : adjs[node]) {
                color[node] = 1;
                if (v != parent) dfs(v, node, res);
                if (isCycle) return true;
            }
            color[node] = 2;
            return false;
        }
    };
    bool validTree(int n, vector<pair<int, int>>& edges) {
        if (edges.size() < n - 1) return false;
        Gragh gragh(n);
        for (auto item : edges) gragh.addEdge(item.first, item.second);
        return gragh.isTreeGragh();
       //return false;
    }

Log in to reply
 

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