1285确定比赛名次 拓扑排序

因为hdu不像leetcode一样 所以自己的思路正确格式出错也没办法

自己的解法是 leetcode 类似题目过了

package leetcode;
import java.util.HashSet;
import java.util.Scanner;
class Node{
  //没有考虑重复为问题
  int val ;
  HashSet<Integer>pre = new HashSet<Integer>();
}
public class test {
  public static void print(Node[]arr) {
      int len = arr.length;
      //次数
      int count = 1;
      StringBuffer sb = new StringBuffer("");
      while( count++ <= len) {
          for(int i = 1; i < len  ; i++) {
              if(arr[i]!=null) {
                  Node temp = arr[i];
                  int val = temp.val;
          //如果入度为0，则输出
                  if(temp.pre.size()==0) {
          //输出结果
                      sb.append(i+" ");
                      arr[i] = null;
          //从头遍历一遍
                      for(int j = 1 ; j < len ;j++) {
                          if(arr[j]!=null) {
          //小心remove索引而不是自己要的值
                              arr[j].pre.remove(val);
                          }
                      }
                  }
              }
          }
      }
      sb.deleteCharAt(sb.length()-1);
      System.out.print(sb.toString());
  }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      while(sc.hasNext()) {
          int N = sc.nextInt();
          int M = sc.nextInt();
          Node [] arr = new Node[N+1];
          //初始化
          for(int i = 1; i < arr.length;i++) {
              arr[i] = new Node();
              arr[i].val = i;
          }

          for(int i = 0 ; i< M ;i++) {
              int x = sc.nextInt();
              int y = sc.nextInt();
              arr[y].pre.add(x);
          }
          print(arr);
          System.out.println();
      }
  }
}

/*
 解题思路： 这是一个典型的拓扑排序，这里我们需要从输入的时候获取没个点的入度，若入度为零的，
              我们可以从小到大依次输出来。每当输出一个点时，需要把它所广联的边全部消除
            （即把该点所相连的点的入度减一），重复上面操作。  
*/
import java.util.Scanner;
public class Main {
  //定义全局变量，方面后面使用
  static int n,m;  //比赛队伍数和输入比赛结果次数
  static int[] degree,sorted; //每个点的入度数和是否被搜索过
  static int[][] arc;   //弧  即点与点之间的联系
  static Scanner sc=new Scanner(System.in);
  public static void main(String[] args) {
      while(sc.hasNext()){
          n=sc.nextInt(); //输入比赛队伍数
          m=sc.nextInt(); //输入比赛过过次数
          init();   //初始化拓扑图
          topoSort(); //拓扑排序
      }
  }
  //拓扑排序
  private static void topoSort() {
      int s=0;//用来记录已经排好序的点的个数
      while(s<n){
          int i=0;
          //1) 找出入度为0的结点
          for(;i<n;i++){//若找到入度为0且没有被搜索过的，获取i值
              if(degree[i]==0&&sorted[i]==0){
                  break;
              }
          }
          if(i==n){//判断是否存在回路,若存在直接返回
              System.out.println("途中存在回路，题目无解！");
              return;
          }
          //2) 出栈，消边(把其所有下级结点的入度减1）
          sorted[i]=1;//搜索过的标记为1
          s++; //排好序的点的个数加一
          System.out.print(i+1); //输出点
          if(s<n){//按题目要求输出空格，最后一个值后面没有空格
              System.out.print(" ");
          }
          //把以i为起点j为终点的边水消去---j的入度减1
          for(int j=0;j<n;j++){
              if(arc[i][j]==1){
                  degree[j]--;
              }
          }
      }
      System.out.println();
  }
  //初始化拓扑图
  private static void init() {
      //初始化
      sorted=new int[n];
      degree=new int[n];
      arc=new int [n][n];
      for(int i=0;i<n;i++){
          sorted[i]=0; //0表示未搜索过，1表示已经搜索过
          degree[i]=0; //入度数，初始化为0
          //初始化点与点之间的联系，初始化为0
          for(int j=0;j<n;j++){
              arc[i][j]=0;
          }
      }
      //接收比赛结果，
      for(int i=0;i<m;i++){
          int a=sc.nextInt()-1;
          int b=sc.nextInt()-1;
          if(arc[a][b]==0){//防止重复比赛结果的输入
              arc[a][b]=1; //对应的点与点之间的联系
              degree[b]++; //对应点入度数加一
          }
      }
  }
}