斯巴达

用户名：AcmeGaga

访问量：1972

签　名：

等　　级
排　　名	5405
经　　验	1544
参赛次数	0
文章发表	22
年　　龄	0
在职情况	学生
学　　校	河南大学
专　　业

　　自我简介：

TA的其他文章

1510: 蓝桥杯算法提高VIP-士兵排队问题(狗币java + 拓扑)
浏览：237

1450: 蓝桥杯2014年第五届真题-矩阵翻硬币 (java, 简单搬运)
浏览：147

1743: 大整数排序 (java的两种实现)
浏览：86

你可能喜欢

A+B for Input-Output Practice (III) （C语言代码）

1510: 蓝桥杯算法提高VIP-士兵排队问题(狗币java + 拓扑)

　　作者: 斯巴达　　　　发表时间：2022-03-22 16:46:54 浏览：237　|　评论：0　

原题链接：蓝桥杯算法提高VIP-士兵排队问题

[https://www.dotcpp.com/oj/problem1510.html](https://www.dotcpp.com/oj/problem1510.html)

- 思路&注意事项
    
    这个道拓扑排序问题, 核心部分与那个卡勒沃夫一样
    
    - 节点标号: 由于是字母, 可以减去'A’来标记节点
    - 遍历后如果有节点的入度不为零说明成环
    
    注意事项
    
    - 输出结果要按照字典序来:
        
        ![Untitled](https://s3.us-west-2.amazonaws.com/secure.notion-static.com/f2d5010b-8b27-48eb-bcac-6a1116a26f1b/Untitled.png?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=AKIAT73L2G45EIPT3X45%2F20220322%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20220322T084514Z&X-Amz-Expires=86400&X-Amz-Signature=4370519df9eb99f2c78a58fde062e6d2c9399c559ee106536cd9990898eab2af&X-Amz-SignedHeaders=host&response-content-disposition=filename%20%3D%22Untitled.png%22&x-id=GetObject)
        
        ![Untitled](https://s3.us-west-2.amazonaws.com/secure.notion-static.com/90374d8c-243f-495a-b3eb-5561a74dfb64/Untitled.png?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=AKIAT73L2G45EIPT3X45%2F20220322%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20220322T084535Z&X-Amz-Expires=86400&X-Amz-Signature=6b28b635b24162f6cc44055624d3886f714a7a1d58b328e3f4646f673428857b&X-Amz-SignedHeaders=host&response-content-disposition=filename%20%3D%22Untitled.png%22&x-id=GetObject)
        
        这种两种情况都要输出ABCD
        
    - 注意这个小坑 `"No Answer!"` 中间一个空格, 不要直接拷贝题目
- 代码
    
    ```java
    import java.util.*;
    
    public class Main {
    	public static void main(String[] args) {
    		Scanner scan = new Scanner(System.in);
    		//初始变量
    		int cnt=0;
    		Node node = new Node();
    		ArrayList<Integer>[] edge = new ArrayList[30];
    		for(int i=0; i< 30; i++) {
    			edge[i] = new ArrayList<Integer>();
    		}
    		//输入
    		while(scan.hasNext()) {
    			String str = scan.next();
    			int i1 = str.charAt(0) - 'A';
    			int i2 = str.charAt(2) - 'A';
    			//i1, i2节点不存在
    			if(!node.nodes.contains(i1)) node.nodes.add(i1);
    			if(!node.nodes.contains(i2)) node.nodes.add(i2);
    			if(str.charAt(1) == '>') {
    				node.out[i1]++; node.in[i2]++;
    				edge[i1].add(i2); edge[i1].sort(null);//要用最小字典序输出, 所以需要排序
    			}else {
    				node.in[i1]++; node.out[i2]++;
    				edge[i2].add(i1); edge[i2].sort(null);
    			}
    		}
    		//把节点顺序调整为字典序
    		node.nodes.sort(null);
    		//创建一个输出队列
    		LinkedList<Integer> output = new LinkedList<>();
    		int index;
    		for(int i=0; i<node.nodes.size(); i++) {
    			index = node.nodes.get(i);
    			//把初始入度为零的节点插入
    			if(node.in[index] == 0)
    				output.addLast(index);
    		}
    		String res = new String();
    		for(int i=0; !output.isEmpty(); i++) {
    			index = output.removeFirst();
    			res += (char)(index + 'A');
    			//index节点的邻接节点in--, 不在output并且in==0 则插入
    			for(int j=0; j<edge[index].size(); j++) {
    				int neighbor = edge[index].get(j);
    				node.in[neighbor]--;
    				if(node.in[neighbor] == 0 && !output.contains(neighbor))
    					output.addLast(neighbor);
    			}			
    		}
    		//当res不为"" && 所有现存节点的入度为0(成环)
    		boolean circle = false;
    		for(int i=0; i<node.nodes.size(); i++) {
    			index = node.nodes.get(i);
    			//获取一个已经存在的节点, 判断是否成环
    			if(node.in[index] != 0) {
    				circle = true; break;
    			}			 
    		}
    		if(res=="" || circle) System.out.println("No Answer!");
    		else System.out.println(res);
    	}
    	static class Node{
    		int[] in = new int[30];
    		int[] out = new int[30];
    		//存放出现过的节点
    		ArrayList<Integer> nodes = new ArrayList<>();
    	}	
    }
    ```

0.0分

0 人评分

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

斯巴达

TA的其他文章

你可能喜欢

C二级辅导-公约公倍（C语言代码）

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

A+B for Input-Output Practice (III) （C语言代码）

不需要数组和指针的做法！！！

【绝对值排序】（C语言代码）

1510: 蓝桥杯算法提高VIP-士兵排队问题(狗币java + 拓扑)

评论区

精彩推荐

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

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

分糖果（C++代码）

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

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

WU-小九九（C++代码）

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

A+B for Input-Output Practice (V) （C语言代码）

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

剪刀石头布（C++代码）

斯巴达

TA的其他文章

你可能喜欢

C二级辅导-公约公倍 （C语言代码）

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

A+B for Input-Output Practice (III) （C语言代码）

不需要数组和指针的做法！！！

【绝对值排序】 （C语言代码）

1510: 蓝桥杯算法提高VIP-士兵排队问题(狗币java + 拓扑)

评论区

精彩推荐

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

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

分糖果 （C++代码）

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

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

WU-小九九 （C++代码）

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

A+B for Input-Output Practice (V) （C语言代码）

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

剪刀石头布 （C++代码）

C二级辅导-公约公倍（C语言代码）

【绝对值排序】（C语言代码）

　　评论区

分糖果（C++代码）

WU-小九九（C++代码）

剪刀石头布（C++代码）