LeetCode 2876: Count Visited Nodes in a Directed Graph Solution

Master LeetCode problem 2876 (Count Visited Nodes in a Directed Graph), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2876. Count Visited Nodes in a Directed Graph

Hard

Dynamic Programming Graph Memoization

Problem Explanation

Explanation

To solve this problem, we can simulate the process of visiting nodes starting from each node. We can use a visited array to keep track of which nodes have been visited. For each node, we follow the directed edges until we reach a node that has been visited before. We count the number of different nodes visited during this process and store it in the answer array.

We initialize an answer array of size n to store the results.
For each node i from 0 to n-1:
- Initialize a visited array of size n to keep track of visited nodes.
- Initialize a count variable to store the number of different nodes visited.
- Start from node i and keep following the directed edges until we reach a visited node.
- Increment the count for each different node visited.
- Store the count in the answer array for node i.
Return the answer array.

Time Complexity: O(n^2) where n is the number of nodes
Space Complexity: O(n)

Solution Code

class Solution {
    public int[] countVisitedNodes(int[] edges) {
        int n = edges.length;
        int[] answer = new int[n];
        
        for (int i = 0; i < n; i++) {
            boolean[] visited = new boolean[n];
            int count = 0;
            int curr = i;
            while (!visited[curr]) {
                visited[curr] = true;
                count++;
                curr = edges[curr];
            }
            answer[i] = count;
        }
        
        return answer;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2876 (Count Visited Nodes in a Directed Graph)?

This page provides optimized solutions for LeetCode problem 2876 (Count Visited Nodes in a Directed Graph) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2876 (Count Visited Nodes in a Directed Graph)?

The time complexity for LeetCode 2876 (Count Visited Nodes in a Directed Graph) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2876 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2876 in Java, C++, or Python.

Back to LeetCode Solutions