题目描述
给出 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]+" ");}}
}