xiaozhuang

用户名：XiaoZhuang23641

访问量：760

签　名：

等　　级
排　　名	36363
经　　验	420
参赛次数	0
文章发表	2
年　　龄	0
在职情况	学生
学　　校	华南师范大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-去注释-题解(Java代码)
浏览：285

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

蓝桥杯算法提高VIP-卡勒沃夫之弱水路三千(提高型)-题解(Java代码)

　　作者: xiaozhuang　　　　发表时间：2020-03-16 18:15:55 浏览：210　|　评论：0　

原题链接：蓝桥杯算法提高VIP-卡勒沃夫之弱水路三千(提高型)

## 拓扑排序算法解决
#### 使用 点和边。复杂度为 O(v+e);
```java
public static void main(String[] args) {

HashMap<String,Integer> map=new HashMap<>();//用于保存名字和序号对应的键值对
        ArrayList<Integer> list= new ArrayList<>();//用于保存拓扑序列
        ArrayList<Integer>[] edge=new ArrayList[105];//保存边。邻接矩阵
        Scanner scan= new Scanner(System.in);
        int T=scan.nextInt();
        int m,n;
        String one,two;
        while(T-->0){
			//每执行一次求顺序，要将所有变量归零初始化。
            map.clear();
            list.clear();
            n=0;
            int[] in=new int[105];//保存入度的数组
            m=scan.nextInt();

for(int i=0;i<105;i++)
                edge[i]=new ArrayList<>();
			//进行输入处理
            while(m-->0){
                one = scan.next();
                two = scan.next();
                if(!map.containsKey(one))map.put(one, n++);//给名字编号
                if(!map.containsKey(two))map.put(two, n++);
                edge[map.get(one)].add(map.get(two));
                in[map.get(two)]++;
            }

//处理拓扑排序，获得拓扑序列
            Queue<Integer> q=new LinkedList<>();//用于保存入度为0的点
            for(int i=0;i<map.size();i++)
                if(in[i]==0)q.add(i);

while(!q.isEmpty()){
                int p=q.poll();//弹出并删除入度为0的点
                list.add(p);
                for(int v: edge[p])
                {
                    in[v]--;
                    if(in[v]==0)q.add(v);
                }
            }

//output，输出处理
            if(list.size()==n){
				//选list 中每一个值，找到对应的String 并输出
                for(int i=0;i<n;i++){
                    String x="";
                    for(String s:map.keySet())
                        if(list.get(i)==map.get(s)){
                            x=s;break;
                        }
					//这里有一点输出的小技巧
                    if(i==n-1)System.out.println(x);
                    else System.out.print(x+" ");

}
            }
            else System.out.println("NO");

}
}
```
[拓扑排序入门](https://blog.csdn.net/qq_41713256/article/details/80805338 "拓扑排序入门")
[参考代码](https://blog.csdn.net/weixin_41793113/article/details/88384863?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task "参考代码")

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

xiaozhuang

TA的其他文章

你可能喜欢

【亲和数】（C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言训练-自由落体问题（C语言代码）

淘淘的名单（C语言代码）答案错误？？？

【亲和数】（C语言代码）

蓝桥杯算法提高VIP-卡勒沃夫之弱水路三千(提高型)-题解(Java代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （Java代码）

哥德巴赫曾猜测（C语言代码）

1157题解

1051（奇了怪了）

字符串的输入输出处理（C语言代码）

GC的苦恼（C语言代码）

第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

小O的乘积（C++代码）

xiaozhuang

TA的其他文章

你可能喜欢

【亲和数】 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言训练-自由落体问题 （C语言代码）

淘淘的名单 （C语言代码）答案错误？？？

【亲和数】 （C语言代码）

蓝桥杯算法提高VIP-卡勒沃夫之弱水路三千(提高型)-题解(Java代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （Java代码）

哥德巴赫曾猜测 （C语言代码）

1157题解

1051（奇了怪了）

字符串的输入输出处理 （C语言代码）

GC的苦恼 （C语言代码）

第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

小O的乘积 （C++代码）

【亲和数】（C语言代码）

C语言训练-自由落体问题（C语言代码）

淘淘的名单（C语言代码）答案错误？？？

【亲和数】（C语言代码）

　　评论区

哥德巴赫曾猜测（C语言代码）

字符串的输入输出处理（C语言代码）

GC的苦恼（C语言代码）

小O的乘积（C++代码）