我是逆过来存的,下面这个版本应该是正确的,本地调试也是要 ctrl + D 结束输入,空间换时间
// 时间限制: 3000MS // 内存限制: 589824KB // 题目描述: // 一般在代码Code Review或者持续集成过程中, // 一次代码提交会触发代码的重新编译及正在Review过程的Pull Request的Approval重置, // 为了加快编译或者只重置受影响的Pull Reqeust,都会进行代码包依赖分析, // 找出受影响的代码包(package)。我们使用正整数表示包,对给定的被修改的包, // 求出所有受影响的包(去重)所代表数字的和,若无受影响的包,则和返回-1。 // 注意,直接依赖及间接依赖的包被修改,当前包均被定义为受影响。 // // 输入描述 // 第一行为整数,代表被修改的包。 // 第二行开始的后续行都是数组,代表数组的第一个元素依赖后续的元素, // 注意数组元素可能只有1个,代表该包无依赖。 // 如输入样例的含义为被修改的包是4, // 包1依赖2, // 包3依赖4、5、6, // 包2依赖3, // 包6依赖4、2, // 包8依赖9, // 包10无依赖。 // // 输出描述 // 所有受影响的包去重后为1、2、3、6,所以其和为12. // // 样例输入 // 4 // 1,2 // 3,4,5,6 // 2,3 // 6,4,2 // 8,9 // 10 // 样例输出 // 12 // 3,6,2,1 // // 提示 // 依赖关系中可能有环,也可能有部分包与其它包之间没有依赖关系。另外,不用考虑求和时整数溢出。
import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { /******************************结束写代码******************************/ public static void main(String[] args){ Scanner in = new Scanner(System.in); String line = in.nextLine(); int target = Integer.parseInt(line.split(" ")[0]); HashMap<Integer,HashSet<Integer>> map = new HashMap<>(); while(in.hasNext()){ String src = in.nextLine(); String []arr = src.split(","); int tt = Integer.parseInt(arr[0]); if(!map.containsKey(tt)){ HashSet<Integer> tmpp = new HashSet<>(); map.put(tt,tmpp); } for (int i = 1; i < arr.length; i++) { int value = Integer.parseInt(arr[i]); if(map.containsKey(value)){ HashSet<Integer> set = map.get(value); set.add(tt); map.put(value,set); }else{ HashSet <Integer>tmpset = new HashSet<>(); tmpset.add(tt); map.put(value,tmpset); } } } Deque<Integer> queue = new LinkedList<>(); queue.offerFirst(target); HashSet<Integer> addbefore = new HashSet<>(); int res = 0; if(!map.containsKey(target)){ System.out.println(0); return; } while(!queue.isEmpty()){ int value = queue.pollLast(); if(map.containsKey(value)) { HashSet<Integer> set = map.get(value); if (!set.isEmpty()) { for (Integer o : set) { System.out.println(o); if (!addbefore.contains(o)) { res += o; queue.offerFirst(o); addbefore.add(o); } } } } } System.out.println(res); } }
全部评论
(1) 回帖