图论练习6

[NOIP2013]车站分级

Here

��解题思路

• 由于起始点之间所选的站号，相互之间一定满足
• 那么对于起始点间未选择的站号，一定满足选择的站号
• 考虑用边来维护信息，表示的级别大于
• 按题意，则车站会被分为几个联通块，且保证块内无环，即一定存在一个有序序列
• 则通过拓扑排序，找到连通块内的最长路径，即为最小的必要分级数

  import java.io.*;import java.math.BigInteger;import java.util.Arrays;import java.util.BitSet;import java.util.HashMap;import java.util.HashSet;import java.util.Iterator;import java.util.LinkedList;import java.util.Map;import java.util.Objects;import java.util.PriorityQueue;import java.util.Queue;import java.util.Random;import java.util.Scanner;import java.util.Stack;import java.util.StringTokenizer;import java.util.Vector;public class Main{static long md=(long)998244353;static long Linf=Long.MAX_VALUE/2;static int inf=Integer.MAX_VALUE/2;public static void main(String[] args) throws IOException{AReader input=new AReader();    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));    /*     * 用有向边维护大于号     * 按题意，则车站会被分为几个联通块，且保证块内无环，即一定存在一个有序序列     * 最长的序列即为最小的必要分级数    */        int n=input.nextInt();    int m=input.nextInt();    boolean[][] e=new boolean[n+1][n+1];    boolean[] vis=new boolean[n+1];    int[] st=new int[n+1];    int[] in=new int[n+1];    for(int i=1;i