2876. Visited Nodes

Prerequisites

我平时不算正经的人 但这次我正经点说

如果2360号这道识别环计算环长的题没掌握好

直接来2876号题 可能被『环』搞到没法生『还』

Count Visited Nodes in a Directed Graph

本难题是这样的 有个总共$n$个且点$n$条边的有向图 点标号是$0$到$n-1$

$n$条边信息都存在名叫edges的阵列

edges[i]是点$i$的出边指向的点标号

并且$edges[i] \neq i$ 说明没有自环点

又 $0 \leq edges[i] \leq n - 1$

因此显然每个点都有 恰好一条出边

现在任务是要我们为所有点计算 从该点出发

一路上能访问多少不同的点

每个点恰好一条出边......那么

相信大家已经能猜到 在这样的先决条件下

站在任何一个环$C$的点上启动DFS

只会在这个$C$兜圈子 毫无机会跳出$C$

由于每个环成员都把唯一出边连给另一个环成员

若环$C$有$k$个成员 显然从这$k$个成员点出发

都仅能网内互打📲 访问$k$个自家人而已

因此一旦识别♻️ 就能整团环的答案一网打尽☑️

非环点又是如何拿捏呢

显而易见 从任何非环点出发 都能访问自己

还有所有儿子能访问到的点

因为老子把唯一的出边留给儿子

儿子唯一的出边留给孙子 没回来找老子🤪

仅剩的难『关』：环的边界感

读到这边 我们自然从前面的解说

意识到 环点和非环点的计数逻辑有差

这时候就到了想个好法子

轻松区分环点和非环点边界感的时候了

我想到的一招是 由儿子结束DFS

往上一层回到老子的那一刻

带一个整数回来给老子当提示

这整数有两种情况：

I. -1：代表儿子不是环成员

于是老子肯定也不是环成员了

II. 一个正整数：代表儿子是环成员了

而这正整数是啥意思呢？

环的起点的访问顺序$d[s]$

事已至此 老子就能拿著自己的访问顺序

来得知自己是否也与儿子一样属环：

(1). 若老子的访问顺序 $\geq d[s]$

那恭喜老子亦是环成员 同时老子要 向上回报$d[s]$

让爷爷跟著判断自己是否也在环内

(2). 若老子的访问顺序 < $d[s]$

那老子就 不是环成员 咯

是把守关内关外界线的山海关

于是老子必须 向上回报-1

告诉上层说自己不是环的一份子

别忘了登出递归栈啊

就和第2360号题一样 每个点结束DFS即将return时

得把自己的访问顺序改成-2 象徵已确实出递归栈

判断环何时成形的逻辑 也与第2360号题一样

每个点每条边各经历一遍 时间复杂度O(V + E)

空间复杂度也呈线性关系 是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