蓝桥训练-拓扑排序-白红宇的个人博客

蓝桥训练-拓扑排序

发布日期：2021-05-14 16:48:52 浏览次数：16 分类：精选文章

本文共 1956 字，大约阅读时间需要 6 分钟。

根据题目要求，下面是关于如何根据士兵的比较结果生成排队方案的详细解释和代码实现：

读取输入数据：我们需要从文本文件中读取所有的比较结果。每行的比较结果格式为“A>B”“B>C”等等。

建立图结构：将这些比较结果转化为图中的有向边。例如，“A>B”表示有向边A指向B。

检查是否存在环：通过进行深度优先搜索（DFS），检查图是否存在环。如果存在环，则问题无解，直接输出“No Answer!”。

进行拓扑排序：如果图是DAG puck，可以使用拓扑排序进行处理。步骤如下：

初始化一个队列，中包含所有入度为0的节点。

将队列中的节点取出，添加到结果顺序中。

对于该节点的所有邻接节点，减少它们的入度。入度为0的节点加入队列，继续处理。

生成排队方案：按照拓扑排序的结果，将所有被选中的节点按顺序连接起来，生成最终的排队方案。

以下是详细的C++代码实现：

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
#include 
        
          #include 
         
           #include 
          
            using namespace std; string topo_sort(int n, vector
           
            
             >& graph) { set
             
               in; for(int i = 1; i <= 26; ++i) { if(in.count(i) == 0) { in.insert(i); queue
              
                q; q.push(i); } while(!q.empty()) { int u = q.front(); q.pop(); res += (char)('A' + u - 1); for(int v : graph[u]) { if(in.count(v) > 0) { --in.count(v); if(in.count(v) == 0) { q.push(v); in.insert(v); } } } } } return res; } int main() { vector
               
                
                 > graph(27, vector
                 
                  (27, 0)); int duin[27] = {0}; char s[5]; while(scanf("%s", s) != EOF) { if(s[0] == '#') break; int a = s[0] - 'A' + 1; int b = s[2] - 'A' + 1; if(a > 26 || b > 26) continue; if(g[a][b] == 0) { g[a][b] = 1; duin[b]++; } if(a > b) { swap(a, b); } if(duin[b] == 0) continue; } set
                  
                    visited; bool isCyclic = false; for(int i = 1; i <= 26; ++i) { if(duin[i] == 0 && visited.find(i) == visited.end()) { queue
                   
                     q; q.push(i); visited.insert(i); bool cycle = false; while(!q.empty()) { int u = q.front(); q.pop(); for(int v : graph[u]) { if(visited.find(v) != visited.end()) { cycle = true; break; } visited.insert(v); q.push(v); } if(cycle) break; } if(cycle) { isCyclic = true; break; } } } if(isCyclic) { printf("No Answer!\n"); return 1; } string res; topo_sort(26, graph); cout << res << '\n'; return 0; }

代码解析：

读取输入：使用scanf读取输入的比较结果，并更新对应的边矩阵graph和每个节点的入度duin。

检测环：使用深度优先搜索（DFS）来检查图是否存在环。如果存在环，输出“No Answer!”。

拓扑排序：使用队列存储入度为0的节点，逐步处理这些节点，添加到结果字符串中，并对其邻接节点的入度进行调整。

生成输出：按拓扑顺序生成的结果字符串构成最终的排队方案，输出到标准输出。

示例输入：

A>B
B>D
F>D

示例输出：

AFBD

上一篇：筛素数，求区间内素数个数

下一篇：蓝桥训练最小生成树kruscal

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章