您的位置:首页 > 文旅 > 美景 > 学平面设计网上哪个培训好_weaver网页制作_星巴克网络营销案例分析_公司网页怎么制作

学平面设计网上哪个培训好_weaver网页制作_星巴克网络营销案例分析_公司网页怎么制作

2024/12/23 12:33:02 来源:https://blog.csdn.net/weixin_65829986/article/details/143761869  浏览:    关键词:学平面设计网上哪个培训好_weaver网页制作_星巴克网络营销案例分析_公司网页怎么制作
学平面设计网上哪个培训好_weaver网页制作_星巴克网络营销案例分析_公司网页怎么制作

题目描述:

某个大型软件项目的构建系统拥有 N 个文件,文件编号从 0 到 N - 1,在这些文件中,某些文件依赖于其他文件的内容,这意味着如果文件 A 依赖于文件 B,则必须在处理文件 A 之前处理文件 B (0 <= A, B <= N - 1)。请编写一个算法,用于确定文件处理的顺序。

输入描述:

第一行输入两个正整数 N, M。表示 N 个文件之间拥有 M 条依赖关系。

后续 M 行,每行两个正整数 S 和 T,表示 T 文件依赖于 S 文件。

输出描述:

输出共一行,如果能处理成功,则输出文件顺序,用空格隔开。

如果不能成功处理(相互依赖),则输出 -1。

输入示例:

5 4
0 1
0 2
1 3
2 4

输出示例:

0 1 2 3 4

拓扑排序步骤:

1、找到入度为0的加入结果集

2、将入度为0的节点从图中移除(这里的移除不是真正的移除,我们将记录每个节点入度数的数组inDgree[i]-1就行了)

代码:

import java.util.*;public class TopoSort {public static void main(String[] args){Scanner scanner=new Scanner(System.in);int n=scanner.nextInt();int m=scanner.nextInt();int[] inDegree=new int[n];List<List<Integer>> umap=new ArrayList<>();for(int i=0;i<n;i++){umap.add(new ArrayList<>());}for(int i=0;i<m;i++){int s=scanner.nextInt();int t=scanner.nextInt();umap.get(s).add(t);inDegree[t]++;}//        拓扑排序Queue<Integer> queue=new LinkedList<>();for(int i=0;i<n;i++){if(inDegree[i]==0) queue.add(i);}List<Integer> res=new ArrayList<>();while(!queue.isEmpty()){int cur=queue.poll();res.add(cur);for(int file:umap.get(cur)){inDegree[file]--;if(inDegree[file]==0){queue.add(file);}}}if(res.size()==n){for(int i=0;i<res.size();i++){System.out.print(res.get(i));if(i<res.size()-1){System.out.println(" ");}}}else{System.out.println(-1);}}
}

如果图中有环,拓扑排序的结果集中的节点会小于总节点数,则输出-1

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com