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<edge>[] map; //表示图
public static ArrayList<String> result1 = new ArrayList<String>(); 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<edge>();
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));
}
}
}
运行结果：
2 5 4
5 1
4 2
1 3
2 3 10 5
4 1
8 1
7 8
4 1
2 8
2 4 5 3 1
5 1 6 2 7 8 3 4 9 10
参考资料：