目录

 

---

1 问题描述

给出一些球，从1~N编号，他们的重量都不相同，也用1~N标记加以区分（这里真心恶毒啊，估计很多WA都是因为这里），然后给出一些约束条件，< a , b >要求编号为 a 的球必须比 b 轻，现在要求按编号升序输出每个球的重量，如果有多种解，输出字典序最小的那个。

例如：

input：

1

5 4

5 1

4 2

1 3

2 3

output：

2 4 5 3 1

 

---

2 解决方案

具体代码如下：

 

package com.liuzhen.practice;import java.util.ArrayList;import java.util.Scanner;public class Main {    public static int count;   //顶点的编号    public static int[] degree;   //计算顶点的入度    public static ArrayList
     
      [] map;  //表示图    public static ArrayList
      
        result1 = new ArrayList
       
        ();        static class edge {        public int a;    //边的起点        public int b;    //边的终点                public edge(int a, int b) {            this.a = a;            this.b = b;        }    }        @SuppressWarnings("unchecked")    public void init(int n) {        count = n;        degree = new int[n + 1];        map = new ArrayList[n + 1];        for(int i = 0;i <= n;i++) {            map[i] = new ArrayList
        
         ();            degree[i] = 0;        }        return;    }        public String getResult() {        String result = "";        int[] ans = new int[degree.length];        while(count >= 1) {            int i = degree.length - 1;            for(;i >= 1;i--) {                if(degree[i] == 0) {                    ans[i] = count--;                    degree[i]--;                    for(int j = 0;j < map[i].size();j++)                        degree[map[i].get(j).b]--;                    break;                }            }            if(i == 0)   //此时给定图存在回环                return "-1";        }        StringBuilder temp = new StringBuilder("");        for(int i = 1;i < ans.length;i++) {            temp.append(ans[i]);            if(i != ans.length - 1)                temp.append(" ");        }        result = temp.toString();        return result;    }        public static void main(String[] args) {        Main test = new Main();        Scanner in = new Scanner(System.in);        int t = in.nextInt();     //要输入图的个数        while(t > 0) {            t--;            int n = in.nextInt();            test.init(n);            int k = in.nextInt();   //输入图的边的个数            for(int i = 0;i < k;i++) {                int a = in.nextInt();                int b = in.nextInt();                boolean judge = true;                for(int j = 0;j < map[b].size();j++) {   //检查重复边                    if(map[b].get(j).b == a){                        judge = false;                        break;                    }                }                if(judge && a != b) {                    map[b].add(new edge(b, a));                    degree[a]++;  //顶点a的入度自增1                }            }            result1.add(test.getResult());        }        for(int i = 0;i < result1.size();i++) {            System.out.println(result1.get(i));        }    }}
        
       
      
     

 

运行结果：

25 45 14 21 32 310 54 18 17 84 12 82 4 5 3 15 1 6 2 7 8 3 4 9 10

 

 

 

 

 

参考资料：

   1.