UVa 792 Program Modules-北京尧图网络

题目描述给定一个程序中的所有函数及其直接调用关系定义关系A→BA \rightarrow BA→B表示函数AAA直接调用BBBA⇒BA \Rightarrow BA⇒B表示AAA可传递地调用BBB直接或间接。已知→\rightarrow→是⇒\Rightarrow⇒的子集且⇒\Rightarrow⇒具有传递性。现需要将所有函数划分为若干模块满足若A⇒BA \Rightarrow BA⇒B且B⇒AB \Rightarrow AB⇒A则AAA与BBB必须在同一模块。任意两个不满足上述条件的函数必须分属不同模块。要求输出所有模块每个模块内的函数名按字典序升序排列模块按第一个元素最小函数名的字典序升序排列。每组数据输出后跟一个空行。输入格式输入包含若干组数据每组数据代表一个待模块化的程序。每组数据格式为(Fun1 Fun11 ... Fun1n1)(Fun2 Fun21 ... Fun2n2)... (Funm Funm1 ... Funmn m).其中每个括号项表示源函数FuniFun_iFuni直接调用其后所有函数FunijFun_{ij}Funijj1..nij 1..n_ij1..ni。函数名由字母组成区分大小写。括号之间、函数名之间可以有任意数量的空格、制表符或换行。每组数据以句点.结尾输入正确每个函数恰好出现在一个项的左侧同一项内函数名互不相同。如果一组数据不含任何括号则表示空函数集例如仅一个.。输出格式对于每组数据输出若干行每行一个模块内的函数名升序排列空格分隔。模块之间按各自最小函数名的字典序升序输出。每组数据的输出结束后必须输出一个空行即使该组没有函数也要输出一个空行。样例输入. (a a) (a b) (b). (a b c) (b a e) (c d) (d d) (e b).输出a b a b e c d题目分析规则1\texttt{1}1和规则2\texttt{2}2共同定义了模块的划分标准若两个函数相互可达即A⇒BA \Rightarrow BA⇒B且B⇒AB \Rightarrow AB⇒A则它们必须在同一模块否则绝对不能在同一模块。这正是有向图中强连通分量Strongly Connected Component\texttt{Strongly Connected Component}Strongly Connected Component,SCC\texttt{SCC}SCC的定义。因此将每个函数看作节点直接调用关系A→BA \rightarrow BA→B看作从AAA到BBB的有向边则一个模块即对应一个强连通分量。由于⇒\Rightarrow⇒是→\rightarrow→的传递闭包同一强连通分量内的任意两个节点相互可达符合规则 1不同强连通分量之间的节点不存在双向可达路径符合规则2\texttt{2}2。因此问题转化为给定有向图求所有强连通分量并按题目要求排序输出。解题思路图构建首先需从输入中提取每个函数及其直接调用列表。输入为自由格式但以句点.分隔每组数据。我们可以先读入整个数据集直到遇到.为一个字符串再通过查找括号(和)来提取每个括号内的内容。每个括号内部是一个空格分隔的单词序列第一个单词为源函数其余为目标函数。为每个函数分配唯一编号建立邻接表。强连通分量求解使用Tarjan\texttt{Tarjan}Tarjan算法求SCC\texttt{SCC}SCC。该算法通过一次深度优先搜索DFS\texttt{DFS}DFS记录每个节点的dfn\textit{dfn}dfn访问次序和low\textit{low}low能回溯到的最早祖先。当dfn[u]low[u]\textit{dfn}[u] \textit{low}[u]dfn[u]low[u]时栈中从栈顶到uuu的所有节点构成一个强连通分量。复杂度为O(VE)O(V E)O(VE)其中VVV为函数数EEE为直接调用边数。排序与输出每个SCC\texttt{SCC}SCC内部函数名按字典序排序整个SCC\texttt{SCC}SCC列表按其最小函数名的字典序排序。输出时每个SCC\texttt{SCC}SCC占一行函数名用空格分隔末尾换行。每组数据结束后额外输出一个空行。复杂度分析解析输入每个字符或单词读入一次时间复杂度O(输入总长度)O(\text{输入总长度})O(输入总长度)。建图每个括号项处理一次总边数EEE时间复杂度O(E)O(E)O(E)。Tarjan\texttt{Tarjan}TarjanO(VE)O(V E)O(VE)。排序每个SCC\texttt{SCC}SCC内部排序总代价O(∑kilog⁡ki)≤O(Vlog⁡V)O(\sum k_i \log k_i) \le O(V \log V)O(∑kilogki)≤O(VlogV)外部排序O(Clog⁡C)O(C \log C)O(ClogC)CCC为SCC\texttt{SCC}SCC数量C≤VC \le VC≤V。总时间复杂度O(VEVlog⁡V)O(V E V \log V)O(VEVlogV)空间复杂度O(VE)O(V E)O(VE)。代码实现// Program Modules// UVa ID: 792// Verdict: Accepted// Submission Date: 2026-07-09// UVa Run Time: 0.300s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorstringsplitByWhitespace(conststrings){vectorstringtokens;stringstreamss(s);string token;while(sstoken)tokens.push_back(token);returntokens;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string data,token;while(cintoken){datatoken;while(1){if(token.back().)break;cintoken;data token;}vectorstringnames;unordered_mapstring,intidMap;vectorvectorintg;autogetNode[](conststringname)-int{autoitidMap.find(name);if(it!idMap.end())returnit-second;intnewId(int)names.size();idMap[name]newId;names.push_back(name);g.push_back({});returnnewId;};size_t pos0;while(true){size_t leftdata.find((,pos);if(leftstring::npos)break;size_t rightdata.find(),left1);string innerdata.substr(left1,right-left-1);vectorstringtokenssplitByWhitespace(inner);if(tokens.empty()){posright1;continue;}intsrcIdgetNode(tokens[0]);for(size_t i1;itokens.size();i){inttIdgetNode(tokens[i]);g[srcId].push_back(tId);}posright1;}intnnames.size();vectorintdfn(n,0),low(n,0),sccId(n,-1),stk;vectorcharinStack(n,0);inttimer0,sccCnt0;functionvoid(int)tarjan[](intu){dfn[u]low[u]timer;stk.push_back(u);inStack[u]1;for(intv:g[u]){if(!dfn[v]){tarjan(v);low[u]min(low[u],low[v]);}elseif(inStack[v]){low[u]min(low[u],dfn[v]);}}if(low[u]dfn[u]){sccCnt;while(true){intvstk.back();stk.pop_back();inStack[v]0;sccId[v]sccCnt;if(vu)break;}}};for(inti0;in;i)if(!dfn[i])tarjan(i);vectorvectorstringsccNodes(sccCnt1);for(inti0;in;i)sccNodes[sccId[i]].push_back(names[i]);for(inti1;isccCnt;i)sort(sccNodes[i].begin(),sccNodes[i].end());vectorintorder(sccCnt);iota(order.begin(),order.end(),1);sort(order.begin(),order.end(),[](inta,intb){returnsccNodes[a][0]sccNodes[b][0];});for(intidx:order){for(intj0;j(int)sccNodes[idx].size();j){if(j)cout ;coutsccNodes[idx][j];}cout\n;}cout\n;}return0;}总结本题本质是图论中的强连通分量求解直接应用Tarjan\texttt{Tarjan}Tarjan算法即可。关键点在于正确解析输入格式将自由格式的括号表达式转化为有向图。输出部分需注意排序规则模块内升序、模块间按最小元素升序和每组数据后的空行。此题提醒我们复杂问题往往能归结为经典算法只要准确建模实现并不困难。

UVa 792 Program Modules

相关推荐

douyin-downloader 免费无水印批量下载：从 0 到增量跟踪的完整教程

UVa 771 Flying Stars

政务文稿场景中，AI辅助工具能做什么、不能做什么

更多资讯

国内高效使用Claude Code AI编程助手的实践指南

ROS 2可靠消息投递机制与wait_for_all_acked实践

Calibre DRC/LVS 验证原理与Runset深度解析

汉字转拼音工具的技术实现与性能优化

机器视觉检测落地：成像、数据与工程化，比算法更关键的三道坎

AI写代码快了十倍，程序员为何更累了？

今日更新

淘宝商品详情API开发实战与性能优化指南

Unity Package Manager刷新错误排查与解决方案

Java record 规范构造器能否被反序列化或反射绕过

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？