题目描述

给出 N 个点，M 条边的有向图，对于每个点 v，求A(v) 表示从点 v 出发，能到达编号最大的点。

思路

既然是要找到最大的点，那么我从最大的点开始DFS是否可以？

于是可以反向建图，然后从最大的节点进行DFS，然后依次往前选择节点DFS。

这个过程中可以用vis[]来看这个节点是否被遍历过，可以用maxRearch来记录最大的编号。

比如我们从最大的节点4开始，在这次DFS中，我们标记当前节点的编号，然后进行遍历，凡是遍历到的，都会被赋予当前节点4。

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;public class Main {public static void main(String[] args) throws IOException {StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));sc.nextToken();int n = (int) sc.nval;sc.nextToken();int m = (int) sc.nval;LinkedList<Integer>[] links = new LinkedList[n+1];for (int i = 1; i <= n; i++) {links[i] = new LinkedList<>();}for (int i = 0; i < m; i++) {sc.nextToken();int begin = (int) sc.nval;sc.nextToken();int end = (int) sc.nval;links[end].add(begin);  //反向建图}boolean[] vis = new boolean[n+1];int[] maxRearch = new int[n+1];Arrays.fill(maxRearch,Integer.MIN_VALUE);Stack<Integer> stack = new Stack<>();for (int j = n; j > 0 ; j--) {//从大的节点往回开始if(!vis[j]){stack.push(j);while(!stack.isEmpty()){int cur = stack.pop();if(vis[cur])    //之前遍历过continuecontinue;maxRearch[cur] = Math.max(maxRearch[cur],j);vis[cur] = true;    //表明遍历过了for (int i = links[cur].size()-1; i >=0 ; i--) {if (vis[cur]){stack.push(links[cur].get(i));}}}}}for (int i = 1; i <=n ; i++) {System.out.print(maxRearch[i]+" ");}}
}