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}Funij​j1..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(∑ki​logki​)≤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算法即可。关键点在于正确解析输入格式将自由格式的括号表达式转化为有向图。输出部分需注意排序规则模块内升序、模块间按最小元素升序和每组数据后的空行。此题提醒我们复杂问题往往能归结为经典算法只要准确建模实现并不困难。