2876. Visited Nodes

Prerequisites

I'm not usually serious. But I am very serious this time.

If you haven't fully grasped problem 2360 about the longest cycle detection,

jumping straight into problem 2876 might leave you stuck in circles with no way out.

Count Visited Nodes in a Directed Graph

A directed graph has $n$ nodes and $n$ edges, with nodes labeled $0$ to $n-1$.

All edge information is stored in an array called edges, where edges[i] is the label of the node to which node $i$'s outgoing edge points.

Also, $edges[i] \neq i$, meaning no self-loops exist.

$0 \leq edges[i] \leq n - 1$, so clearly every node has exactly one outgoing edge.

Our task is to compute, for every node,

how many distinct nodes can be visited starting from that node and following edges.

Every Node Has Just An Outgoing Edge... So

You've probably already guessed it: by this constraint,

starting DFS from any node inside a cycle $C$ will only loop within $C$: no way to escape.

Since every cycle member's sole outgoing edge points to another cycle member,

if cycle $C$ has $k$ members, then from any of those $k$ nodes, you can only reach these $k$ members within this cycle 📲

So once a cycle is identified ♻️, the answer to this entire cycle can be resolved at once ☑️.

What About Non-Cycle Nodes?

Obviously, starting from any non-cycle node, you can visit yourself,

plus all the nodes reachable through your child.

Because a parent's only outgoing edge goes to the child, and the child's only outgoing edge goes to the grandchild, instead of coming back to its parent.

The Last Hurdle: Knowing Cycle's Boundary

At this point, we naturally realize from the discussion above that cycle nodes and non-cycle nodes have different counting logic.

Now comes the tricky part: find a clean way to easily tell apart the boundary between cycle and non-cycle nodes.

My approach: when a child finishes DFS and returns to its parent,

it passes back an integer as a hint.

This integer has two cases:

I. -1: child is not a cycle member.

So the parent is definitely not a cycle member.

II. A positive integer: child is a cycle member.

What does this integer represent?

Visit order $d[s]$ of the cycle's starting node.

With this, the parent can use its own visit order to determine whether it also belongs to the same cycle as its child:

(1). If the parent's visit order $\geq d[s]$,

the parent is also a cycle member, so it should pass $d[s]$ upward to let its grandparent also check cycle membership.

(2). If the parent's visit order $< d[s]$,

then the parent is not a cycle member.

This parent is the boundary between inside and outside the cycle.

So the parent must pass -1 upward, telling all layers above that it is not part of cycle.

Don't Forget to Pop Off the Stack

Just like in problem 2360, when a node finishes DFS and is about to return,

its visit order must be set to -2, marking it as truly off the recursion stack.

The logic to detect when a cycle forms is identical to problem 2360.

Each node and each edge is traversed exactly once. Time complexity is $O(V + E)$.

Space complexity is also linear: $O(V + E)$.

C++

#include <vector>
using namespace std;

class DirectedGraphVisitedNodes // LeetCode Q.2876.
{
private:
    vector<int> graph, visitedOrders, visitedCounts;
    int currentOrder = 1;

    int dfsVisitedNodes(int node) {
        visitedOrders[node] = currentOrder;
        currentOrder++;

        int cycleStartOrder = -1;

        int tgtNode = graph[node];
        if (visitedOrders[tgtNode] == -1) // Unvisited target node.
            cycleStartOrder = dfsVisitedNodes(tgtNode);

        // A cycle just forms. Current node and its target node are members.
        if (visitedOrders[tgtNode] > 0) {
            int cycleSize = visitedOrders[node] + 1 - visitedOrders[tgtNode];
            visitedCounts[node] = cycleSize;

            visitedOrders[node] = -2; // Current node has finalized DFS.

            return visitedOrders[tgtNode]; // Where cycle starts.
        }

        // Reset: current node is no part of any cycle. Nor are its ascendants.
        if (visitedOrders[node] < cycleStartOrder)
            cycleStartOrder = -1;

        visitedCounts[node] = visitedCounts[tgtNode];
        if (cycleStartOrder == -1)
            visitedCounts[node]++;

        visitedOrders[node] = -2; // Current node has finalized DFS.
        return cycleStartOrder;
    }

public:
    vector<int> countVisitedNodes(vector<int>& edges) {
        graph = edges;
        visitedCounts.assign(edges.size(), 0);

        // Special marks: -1 = unvisited yet. -2 = has finalized DFS.
        visitedOrders.assign(edges.size(), -1);

        for (int node = 0; node < graph.size(); node++)
            if (visitedOrders[node] == -1)
                dfsVisitedNodes(node);

        return visitedCounts;
    }
};

Python

class DirectedGraphVisitedNodes:  # LeetCode Q.2876.
    def __init__(self):
        self.graph: list[int] = []
        self.visited_orders: list[int] = []
        self.current_order = 1
        self.visited_counts: list[int] = []

    def _dfs_visited_nodes(self, node: int) -> int:
        self.visited_orders[node] = self.current_order
        self.current_order += 1

        cycle_start_order = -1

        target_node = self.graph[node]
        if self.visited_orders[target_node] == -1:  # Unvisited target node.
            cycle_start_order = self._dfs_visited_nodes(target_node)

        # A cycle just forms. Current node and its target node are members.
        if self.visited_orders[target_node] > 0:
            cycle_size = self.visited_orders[node] + 1 - self.visited_orders[target_node]
            self.visited_counts[node] = cycle_size

            self.visited_orders[node] = -2  # Current node has finalized DFS.

            return self.visited_orders[target_node]  # Where cycle starts.

        # Reset: current node is no part of any cycle. Nor are its ascendants.
        if self.visited_orders[node] < cycle_start_order:
            cycle_start_order = -1

        self.visited_counts[node] = self.visited_counts[target_node]
        if cycle_start_order == -1:
            self.visited_counts[node] += 1

        self.visited_orders[node] = -2  # Current node has finalized DFS.
        return cycle_start_order

    def count_visited_nodes(self, edges: list[int]) -> list[int]:
        self.graph = edges
        self.visited_counts = [0] * len(edges)

        # Special marks: -1 = unvisited yet. -2 = has finalized DFS.
        self.visited_orders = [-1] * len(edges)
        self.current_order = 1

        for node in range(len(edges)):
            if self.visited_orders[node] == -1:
                self._dfs_visited_nodes(node)

        return self.visited_counts