Graph Valid Tree - Kiểm tra đồ thị có phải cây hợp lệ

Cho n nút (0..n-1) và danh sách cạnh vô hướng. Kiểm tra xem có tạo thành cây hợp lệ không (liên thông, không chu trình).

Ví dụ: n=5, edges=[[0,1],[0,2],[0,3],[1,4]] → true.

Giải thuật (DFS phát hiện chu trình + kiểm tra liên thông)

DFS với 3 trạng thái: 0=chưa thăm, 1=đã xong, 2=đang thăm. Nếu gặp nút trạng thái 2 → có chu trình. Sau DFS, kiểm tra tất cả nút đã thăm (liên thông).

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool dfs(int node, int par, vector<int> graph[], vector<int>& visited) {
        if (visited[node] == 1) return true;
        if (visited[node] == 2) return false;
        visited[node] = 2;
        bool ret = true;
        for (int v : graph[node])
            if (v != par)
                ret &= dfs(v, node, graph, visited);
        visited[node] = 1;
        return ret;
    }

    bool validTree(int n, vector<vector<int>>& edges) {
        vector<int> visited(n, 0);
        vector<int> graph[n];
        for (auto& e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }
        if (!dfs(0, -1, graph, visited)) return false;
        for (int i = 0; i < n; i++)
            if (!visited[i]) return false;
        return true;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{0,1},{0,2},{0,3},{1,4}};
    cout << ob.validTree(5, v);
    return 0;
}

Đầu vào

5, {{0,1},{0,2},{0,3},{1,4}}

Đầu ra

1