<commit_before>// Time:  O(|V| + |E|)
// Space: O(|V|)

class Solution {
public:
    struct node {
        int parent;
        vector<int>neighbors;
    };
    bool validTree(int n, vector<pair<int, int>>& edges) {
        if (edges.size() != n - 1) {
            return false;
        }

        unordered_map<int,node> nodes;
        unordered_set<int> visited;
        for (const auto& edge : edges) {
            nodes[edge.first].neighbors.emplace_back(edge.second);
            nodes[edge.second].neighbors.emplace_back(edge.first);
        }
        for (int i = 0; i < n; ++i) {
            nodes[i].parent = -1;
        }

        queue<int> q;
        q.emplace(0);
        visited.insert(0);
        while (!q.empty()) {
            int i = q.front();
            q.pop();
            for (const auto& n : nodes[i].neighbors) {
                if (n != nodes[i].parent) {
                    if (visited.find(n) != visited.end()) {
                        return false;
                    } else {
                        visited.insert(n);
                        nodes[n].parent = i;<commit_msg>Update graph-valid-tree.cpp<commit_after>// Time:  O(|V| + |E|)
// Space: O(|V|)

class Solution {
public:
    struct node {
        int parent;
        vector<int>neighbors;
    };
    bool validTree(int n, vector<pair<int, int>>& edges) {
        if (edges.size() != n - 1) {
            return false;
        }

        unordered_map<int,node> nodes;
        for (const auto& edge : edges) {
            nodes[edge.first].neighbors.emplace_back(edge.second);
            nodes[edge.second].neighbors.emplace_back(edge.first);
        }
        for (int i = 0; i < n; ++i) {
            nodes[i].parent = -1;
        }

        unordered_set<int> visited;
        queue<int> q;
        q.emplace(0);
        while (!q.empty()) {
            int i = q.front();
            q.pop();
            visited.insert(i);
            for (const auto& n : nodes[i].neighbors) {
                if (n != nodes[i].parent) {
                    if (visited.find(n) != visited.end()) {
                        return false;
                    } else {
                        visited.insert(n);
                        nodes[n].parent = i;
{'fraction_non_alphanumeric': 0.14713774597495527, 'fraction_numerical': 0.004025044722719142, 'mean_word_length': 1.3671957671957673, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1425786', 'n_tokens_mistral': 718, 'n_tokens_neox': 692, 'n_words': 146}