拓扑排序之车站分级

P1983 [NOIP2013 普及组] 车站分级 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

由于Java速度的局限性，即使我写了基础的快读快输，仍然在第8个样例点处tle

大家可以自行去洛谷下载来验证

思路是这样的，我们把所有列车未停靠的车站指向已经停靠的车站，在这里，我们要记住去重，然后我们记录这些车站的先后关系。设置分级数组，默认每个车站的等级是一级，然后我们开始拓扑排序，a号车站链接的b号车站的等级等于b号的等级和a号车站的等级加1做对比取最大。

为什么呢，原因很简单，要最小的分级数量，那么我们就加一即可。

代码

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.math.MathContext;
import java.security.PublicKey;
import java.sql.SQLIntegrityConstraintViolationException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;
 
import javax.sound.midi.Soundbank;
public class Main {	
  public static void main(String[] args) throws NumberFormatException, IOException  {
Scanner sc=new Scanner(System.in);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw1=new PrintWriter(System.out);
String[] aStrings=br.readLine().split(" ");
aa=Integer.parseInt(aStrings[0]);
bb=Integer.parseInt(aStrings[1]);
al1=new ArrayList[aa+1];
visited=new int[aa+1];
rudu=new int[aa+1];
answer=new int[aa+1];
cc=new int[aa+1][aa+1];
int a,b,c,d,e,f,g;
for(a=1;a<=aa;a++) {
	al1[a]=new ArrayList<>();
}
for(a=0;a<bb;a++) {//这就是用来存储边的过程
	String[] bStrings=br.readLine().split(" ");
	b=Integer.parseInt(bStrings[0]);
	c=bStrings.length;
	Arrays.fill(visited, 0);
	for(d=1;d<c;d++) {
		e=Integer.parseInt(bStrings[d]);
		visited[e]=1;
	}
	f=Integer.parseInt(bStrings[1]);
	g=Integer.parseInt(bStrings[c-1]);
	for(int a1=f;a1<=g;a1++) {
		if(visited[a1]==0) {
			for(int b1=1;b1<c;b1++) {
				int c1=Integer.parseInt(bStrings[b1]);
				if(cc[a1][c1]==0) {
					cc[a1][c1]=1;
					al1[a1].add(c1);
					rudu[c1]++;
				}
			}
		}
	}
}
tuopu();
int answer3=0;
for(int c22=1;c22<=aa;c22++) {
	answer3=Math.max(answer3, answer[c22]);
}
System.out.println(answer3);
}
public static int aa,bb;  //记录车站的数量和几条路线
public static ArrayList<Integer>[] al1;//存储边
public static LinkedList<Integer> ll1=new LinkedList<>();//存储入度为0的点
public static int[] rudu;//入度数组
public static int[] answer;//每个点的等级数组
public static int[][] cc;//判断是否已经存入a到b的一条边，这个数组是为了我们来去重边时所用
public static int[] visited;//判断一条路线中已经被经过的车站的编号
public static void tuopu() {
	int a;
	Arrays.fill(answer, 1);//初始把每个车站的等级设为1级。
	for(a=1;a<=aa;a++) {
		if(rudu[a]==0) {
		ll1.add(a);
		}
	}
	while(ll1.size()!=0) {//取出入度为0的点
		int d=ll1.remove();
		for(int c:al1[d]) {
			rudu[c]--;
			answer[c]=Math.max(answer[c], answer[d]+1);//不断更新等级
			if(rudu[c]==0) {//入度为0了，那么就继续汪队列里面添加
				ll1.add(c);
			}
		}
	}
}
}