题目思路

本题难度非常大，需要对图论有较深的理解，不建议初学者尝试。你需要提前了解拓扑排序以及关键路径的相关知识。

我们拓扑排序后可以得到一个序列，并通过这个序列的我们可以计算得到每个点的最早开始时间和最晚开始时间。一个点的最早开始时间和最晚开始时间相等时，我们称这个点是关键路径上的点，关键路径同时也是最长的路径。

对于一个超级快递点y，假设其在拓扑排序中的序列的位置是x，那么[1,x-1]对应的点都可以到达y，且y可以到达所有[x + 1,n]的点。

超级快递点有一个性质，那就是它肯定是关键路径上的点，我们可以假设前面属于关键路径上的点形成一条链，后面属于关键路径上的点形成一条链，那么由于关键路径是最长的，所以经过点y肯定比不经过点y更长。 但是这只是一个必要条件，还存在以下的平行的特殊情况：

1. 点y和点z平行，即1 -> y -> 2，1 -> z -> 2，y和z完全平行，此时y不可以到达z，z也不可以到达y，但是它们确实满足最早开始时间和最晚开始时间相等，这种情况下的y和z的最早开始时间也相等，我们可以根据最晚开始时间排序后相邻且相等的时间来排除。
2. 点y和点z平行，但是是两条路径平行，比如 1 -> 2 -> y -> 6, 3 -> z -> 5，此时y在关键路径上，但是它不是超级快递点，此时z和它平行，此时z和y的最晚开始时间相同，但是z的最早时间却比y更早，那就说明存在一条比关键路径更短的平行路径，且y就在平行路径中。

所以对于关键路径上的点y，如果有点和它的最早开始时间和最晚开始时间都是相同的，又或者说出现了最晚开始时间大于等该点的点z，z的最早开始时间却小于等于点y的最早开始时间，那这个点就不是超级快递点。

平行路径上的点y只要不平行于其它节点，那从拓扑排序中点y前面的点肯定可以到达它，我们通过反证法证明，如果前面有一个点z到达不了点y，说明z可以跨过y到达后面的终点，这就是另外一个平行点，这与y没有平行点冲突，后面的点可以到达y也是同样的道理。

所以我们通过最晚完成时间，最早完成时间进行两个关键字排序，枚举关键路径上的每一个点，当这个点不存在平行点时，就将其加入到答案中。

时间复杂度$O(nlogn)$

代码

C++

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using u64 = uint64_t;


void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
    }
    // 拓扑排序
    vector<int> ind(n, 0);
    for (int i = 0; i < n; i++) {
        for (int v : adj[i]) ind[v]++;
    }
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (!ind[i]) q.push(i);
    }
    vector<int> ord;
    for (int i = 0; i < n; i++) {
        int u = q.front(); q.pop();
        ord.push_back(u);
        for (int v : adj[u]) {
            if (--ind[v] == 0) {
                q.push(v);
            }
        }
    }
    // 计算最早开始时间和最晚开始时间
    vector<int> min_time(n, 0), max_time(n, 0);
    int tot = 0;
    for (int i = 0; i < n; i++) {
        for (int j : adj[ord[i]]) {
            min_time[j] = max(min_time[j], min_time[ord[i]] + 1);
            tot = max(tot, min_time[j]);
        }
    }
    max_time = vector<int>(n, tot);
    for (int i = n - 1; i >= 0; i--) {
        for (int j : adj[ord[i]]) {
            max_time[ord[i]] = min(max_time[ord[i]], max_time[j] - 1);
        }
    }
    int ans = 0;
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    // 根据最晚开始时间排序
    sort(idx.begin(), idx.end(), [&](int x, int y) {
    	if (max_time[x] != max_time[y]) return max_time[x] > max_time[y];
    	return min_time[x] < min_time[y];
    });
    for (int i = 0, l = 0x3f3f3f3f; i < n; i++) {
    	int j = idx[i];
    	// 超级快递点必定满足最早开始时间和最晚开始时间相同
        if (min_time[j] != max_time[j]) {
        	l = min(min_time[j], l);
        	continue;
        }
        // 除去平行链路情况
        if (l <= min_time[j]) continue; // 题解中的第二种情况
        l = min_time[j];
        // 题解中的第一种情况
        if (i + 1 < n && max_time[j] == max_time[idx[i + 1]] && min_time[j] == min_time[idx[i + 1]]) continue;
        ++ ans;
    }
    cout << ans << endl;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
    while (t--) {
    	solve(); 
	}
}

java

import java.util.*;

public class Main {

    public static void solve() {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();  // 节点数量
        int m = scanner.nextInt();  // 边的数量
        List<List<Integer>> adj = new ArrayList<>();  // 邻接表表示的图

        // 初始化邻接表
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        // 读取边的信息，并更新邻接表
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt() - 1;  // 起点（将1-based转为0-based）
            int v = scanner.nextInt() - 1;  // 终点（将1-based转为0-based）
            adj.get(u).add(v);  // 将边u->v添加到邻接表中
        }

        // 拓扑排序
        int[] ind = new int[n];  // 入度数组
        for (int i = 0; i < n; i++) {
            for (int v : adj.get(i)) {
                ind[v]++;  // 计算每个节点的入度
            }
        }

        Queue<Integer> q = new LinkedList<>();  // 用于存储入度为0的节点
        for (int i = 0; i < n; i++) {
            if (ind[i] == 0) {
                q.add(i);  // 入度为0的节点加入队列
            }
        }

        List<Integer> ord = new ArrayList<>();  // 用于存储拓扑排序后的节点顺序
        while (!q.isEmpty()) {
            int u = q.poll();  // 取出一个入度为0的节点
            ord.add(u);  // 将该节点加入拓扑排序序列
            for (int v : adj.get(u)) {
                if (--ind[v] == 0) {
                    q.add(v);  // 如果v的入度减为0，则加入队列
                }
            }
        }

        // 计算最早开始时间和最晚开始时间
        int[] minTime = new int[n];  // 存储每个节点的最早开始时间
        int[] maxTime = new int[n];  // 存储每个节点的最晚开始时间
        Arrays.fill(maxTime, 0);  // 初始化最晚开始时间为0

        int tot = 0;  // 记录整个图的最长路径
        // 计算最早开始时间
        for (int i = 0; i < n; i++) {
            int u = ord.get(i);  // 根据拓扑顺序遍历
            for (int v : adj.get(u)) {
                minTime[v] = Math.max(minTime[v], minTime[u] + 1);  // 更新最早开始时间
                tot = Math.max(tot, minTime[v]);  // 更新最长路径的长度
            }
        }

        Arrays.fill(maxTime, tot);  // 初始化所有节点的最晚开始时间为总最长路径长度
        // 计算最晚开始时间
        for (int i = n - 1; i >= 0; i--) {
            int u = ord.get(i);  // 逆拓扑顺序遍历
            for (int v : adj.get(u)) {
                maxTime[u] = Math.min(maxTime[u], maxTime[v] - 1);  // 更新最晚开始时间
            }
        }

        int ans = 0;  // 记录最终答案，即超级快递点的数量
        Integer[] idx = new Integer[n];  // 用于存储节点索引
        for (int i = 0; i < n; i++) {
            idx[i] = i;  // 初始化为0到n-1的索引
        }

        // 根据最晚开始时间进行排序
        Arrays.sort(idx, (x, y) -> {
            if (maxTime[x] != maxTime[y]) return Integer.compare(maxTime[y], maxTime[x]);
            return Integer.compare(minTime[x], minTime[y]);
        });

        int l = Integer.MAX_VALUE;  // 初始化最小开始时间限制
        for (int i = 0; i < n; i++) {
            int j = idx[i];
            // 超级快递点必须满足最早开始时间和最晚开始时间相同
            if (minTime[j] != maxTime[j]) {
                l = Math.min(minTime[j], l);
                continue;
            }
            // 如果当前最小开始时间限制小于等于当前节点的最早开始时间，跳过此节点
            if (l <= minTime[j]) continue;
            l = minTime[j];
            // 排除平行链路的情况
            if (i + 1 < n && maxTime[j] == maxTime[idx[i + 1]] && minTime[j] == minTime[idx[i + 1]]) continue;
            ans++;  // 增加超级快递点计数
        }

        System.out.println(ans);  // 输出超级快递点数量
    }

    public static void main(String[] args) {
        solve();  // 执行解决方案
    }
}

题目描述

快递站共有$n$个快递点，$n$个快递点之间通过$m$条个快递站单向车道连接，快递员从任何一个快递站点出发，都无法通过单向车道回到该站点。也就是说，$n$个快递点组成一张有向无环图。对于快递点$u$，如果对于所有的快递点$v(v≠u)$，快递员都可以从$u$走到$v$，或者从$v$走到$u$，那么则评定站点$u$为超级快递点。请你帮忙计算，一共有多少个超级快递点。

输入描述

第一行 2个数字$n(2≤n≤3*10^5)$，

$m(1≤m<3*10^5)$;n为快递点个数，m为单向车道个数

接下来的$m$行每行两个数字$u,v(1≤u,v≤n,u≠v)$，表示有一条站点$u$指向$v$的单向车道。

输出描述

请输出1个数字，表示超级快递点的个数。

样例

输入

7 7
1 2
2 3
3 4
4 7
2 5
5 4
6 4

输出

2

说明

快递点4可以到达 4，7，可以从1，2，3，5，6到达，评为超级快递点
快递点7可以到达7，可以从1，2，3，4，5，6到达，评为超级快递点