Time Taken to Mark All Nodes solution and explanation

from collections import deque

def mark_all_nodes_bfs(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    def bfs(start):
        time = [-1] * n
        queue = deque([(start, 0)])
        time[start] = 0

        while queue:
            node, t = queue.popleft()
            for neighbor in graph[node]:
                if time[neighbor] == -1:
                    if neighbor % 2 == 0:
                        new_time = t + 2
                    else:
                        new_time = t + 1

                    if time[neighbor] == -1 or new_time < time[neighbor]:
                        time[neighbor] = new_time
                        queue.append((neighbor, new_time))
        return max(time)

    result = []
    for i in range(n):
        result.append(bfs(i))
    return result

function markAllNodesBFS(n, edges) {
    const graph = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }

    function bfs(start) {
        const time = Array(n).fill(-1);
        const queue = [[start, 0]];
        time[start] = 0;

        while (queue.length) {
            const [node, t] = queue.shift();
            for (const neighbor of graph[node]) {
                if (time[neighbor] === -1) {
                    const newTime = neighbor % 2 === 0 ? t + 2 : t + 1;
                    if (time[neighbor] === -1 || newTime < time[neighbor]) {
                        time[neighbor] = newTime;
                        queue.push([neighbor, newTime]);
                    }
                }
            }
        }
        return Math.max(...time);
    }

    const result = [];
    for (let i = 0; i < n; i++) {
        result.push(bfs(i));
    }
    return result;
}

import java.util.*;

public class Solution {
    public int[] markAllNodesDFS(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = dfs(i, graph, new boolean[n]);
        }
        return result;
    }

    private int dfs(int node, List<List<Integer>> graph, boolean[] visited) {
        visited[node] = true;
        int time = 0;
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                int neighborTime = neighbor % 2 == 0 ? dfs(neighbor, graph, visited) + 2 : dfs(neighbor, graph, visited) + 1;
                time = Math.max(time, neighborTime);
            }
        }
        visited[node] = false;
        return time;
    }
}

#include <vector>
#include <algorithm>

std::vector<int> markAllNodesDFS(int n, const std::vector<std::vector<int>>& edges) {
    std::vector<std::vector<int>> graph(n);
    for (const auto& edge : edges) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }

    std::vector<int> result(n);
    for (int i = 0; i < n; ++i) {
        std::vector<bool> visited(n, false);
        result[i] = dfs(i, graph, visited);
    }
    return result;
}

int dfs(int node, const std::vector<std::vector<int>>& graph, std::vector<bool>& visited) {
    visited[node] = true;
    int time = 0;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            visited[neighbor] = true;
            int neighborTime = (neighbor % 2 == 0) ? dfs(neighbor, graph, visited) + 2 : dfs(neighbor, graph, visited) + 1;
            time = std::max(time, neighborTime);
        }
    }
    visited[node] = false;
    return time;
}