Java实现Labeling Balls(拓扑排序的应用)
2023-09-14 08:58:12 时间
1 问题描述
给出一些球,从1N编号,他们的重量都不相同,也用1N标记加以区分(这里真心恶毒啊,估计很多WA都是因为这里),然后给出一些约束条件,< a , b >要求编号为 a 的球必须比 b 轻,现在要求按编号升序输出每个球的重量,如果有多种解,输出字典序最小的那个。
例如:
input:
1
5 4
5 1
4 2
1 3
2 3
output:
2 4 5 3 1
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));
}
}
}
运行结果:
4
1
2
3
3
5
1
1
8
1
8
4 5 3 1
1 6 2 7 8 3 4 9 10
相关文章
- Java进阶(二十三)java中long类型转换为int类型
- java 四舍五入运算_JAVA正确的四舍五入方法「建议收藏」
- java random函数用法_JAVA的Random类的用法详解[通俗易懂]
- Java map集合深入学习
- 基于Java swing+mysql+eclipse的【图书管理系统】
- java生成时间戳类型_Java获取当前时间戳的方法有哪些
- think in java一_Think in Java(一):Java基础「建议收藏」
- java 二维数组 arraycopy_Java对数组的复制[通俗易懂]
- java环境_Java 开发环境配置
- java 中高级面试题_Java中高级面试题
- java public interface_Java 接口interface的基础[通俗易懂]
- java文件上传服务器路径,java文件上传服务器路径地址「建议收藏」
- java 读取字符串文件_Java读取文件为字符串
- 【说站】java Function怎么用?
- JAVA实验室设备管理系统代码_java做一个简单学生管理系统
- Java截取字符串方法_java通过split截取字符串
- Hbase For Java详解大数据
- [十五]java.math包简介,RoundingMode与MathContext详解编程语言
- 深入Linux环境下Java应用调试实践(linux调试java)
- 持久化Java持久化技术与Redis高级应用(redis高级之java)
- 机制深度剖析Redis Java过期机制.(redisjava过期)
- 缓存实现面向Java应用的Redis过期缓存技术(redisjava过期)
- 服务器快速搭建Linux Java服务器,实现互联网应用(linux搭建java)
- 策略实现Java应用的Redis过期策略(redisjava过期)
- Java实现Redis数据存储(java的redis)
- 版本Linux查看Java版本的简单方法(linux 查看java)
- Java程序调用Linux系统命令实现更多功能(java调用linux命令)