题目分析本题要求根据通话记录找出所有“通话圈”。所谓“通话圈”是指一组人其中任意两人之间可以通过直接或间接的通话互相联系。更精确地说如果两个人之间存在一条有向路径从AAA到BBB同时也存在一条有向路径从BBB到AAA那么AAA和BBB属于同一个通话圈。题目输入包含多个数据集每个数据集先给出人数nnn和通话记录数mmm然后是mmm行通话记录每行两个名字表示一次通话从第一个人打给第二个人。当n0n 0n0且m0m 0m0时输入结束。输出时每个数据集先输出标题行然后每行输出一个通话圈的所有名字名字之间用 “,”逗号加空格分隔不同数据集之间用空行分隔。关键点有向图模型每个人是图的一个顶点每条通话记录u→vu \rightarrow vu→v是一条有向边。强连通分量的定义题目描述的“通话圈”本质上就是有向图中的强连通分量Strongly Connected ComponentSCC\texttt{Strongly Connected ComponentSCC}Strongly Connected ComponentSCC即分量内任意两个顶点uuu和vvv都互相可达存在uuu到vvv的路径和vvv到uuu的路径。人数限制n≤25n \leq 25n≤25数据规模很小可以采用 Floyd 算法求传递闭包。输入输出细节名字是大小写敏感的只包含字母长度不超过252525。每个数据集可能包含的名字数量可能少于给定的nnn从样例可以看出实际的nnn是根据输入的边去重后的人数而不是第一行给的nnn。代码中通过动态分配索引来解决这个问题将第一行的nnn实际上用于初始化但后续重新计算为实际人数。输出顺序没有严格要求但通常按照每个分量中第一个出现的人名顺序输出。解题思路思路概述由于n≤25n \leq 25n≤25我们可以使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法来计算所有点对之间的可达性即传递闭包。然后对于每一对顶点(i,j)(i, j)(i,j)如果iii可达jjj且jjj可达iii则iii和jjj属于同一个强连通分量。具体步骤1. 数据读取与建图使用mapstring, int\texttt{mapstring, int}mapstring, int将每个名字映射到整数编号。使用mapint, string\texttt{mapint, string}mapint, string将编号映射回名字便于输出。邻接矩阵edges[i][j]\texttt{edges[i][j]}edges[i][j]初始化为一个大数如100001000010000表示不可达。当读入一条通话u→vu \rightarrow vu→v时设置edges[u][v]1\texttt{edges[u][v]} 1edges[u][v]1。2.Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall求传递闭包Floyd 算法的核心思想是动态规划设edges[i][j]\texttt{edges[i][j]}edges[i][j]表示从iii到jjj的最短路径长度或是否存在路径。对于本题我们只关心是否存在路径因此可以将edges[i][j]\texttt{edges[i][j]}edges[i][j]初始化为∞\infty∞不可达或111直接可达然后通过以下方式更新edges[i][j]min⁡(edges[i][j], edges[i][k]edges[k][j]) edges[i][j] \min(edges[i][j],\; edges[i][k] edges[k][j])edges[i][j]min(edges[i][j],edges[i][k]edges[k][j])如果最终edges[i][j]∞\texttt{edges[i][j]} \inftyedges[i][j]∞则iii可达jjj。由于nnn很小三重循环O(n3)O(n^3)O(n3)完全可行2531562525^3 1562525315625次操作。3. 寻找强连通分量对于每个未输出的顶点iii创建一个新的分量将iii加入。然后遍历所有其他未输出的顶点jjj如果edges[i][j]∞\texttt{edges[i][j]} \inftyedges[i][j]∞且edges[j][i]∞\texttt{edges[j][i]} \inftyedges[j][i]∞则jjj与iii互相可达属于同一分量将其加入并标记为已输出。注意这种做法的正确性依赖于Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法已经计算了所有可达性。由于传递闭包具有传递性如果iii和jjj互相可达iii和kkk互相可达则jjj和kkk也必然互相可达。因此我们只需要以每个分量的“代表元”为基准收集所有与其互相可达的点即可。4. 输出格式按照题目要求每个分量的名字以 “,” 分隔一行输出一个分量。不同数据集之间输出一个空行第一个数据集之前不需要空行。代码实现Folyd-Warshall\texttt{Folyd-Warshall}Folyd-Warshall算法// Calling Circles// UVa ID: 247// Verdict: Accepted// Submission Date: 2016-05-10// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN10000;// 定义一个大数表示无穷大不可达intedges[25][25];// 邻接矩阵存储有向边的权重1 表示直接可达mapstring,intindexer;// 名字 - 编号mapint,stringnames;// 编号 - 名字intn,m;// n 为实际人数m 为通话记录数// Floyd-Warshall 算法求所有点对之间的最短路径长度// 由于边权为 1最终 edges[i][j] MAXN 表示 i 可达 jvoidfloyd(){for(intk0;kn;k)for(inti0;in;i)for(intj0;jn;j)if(edges[i][k]edges[k][j]edges[i][j])edges[i][j]edges[i][k]edges[k][j];}// 找出所有强连通分量通话圈并输出voidfindAllCircles(){floyd();// 先计算传递闭包vectorbooloutputed(n);// 标记每个顶点是否已经被输出fill(outputed.begin(),outputed.end(),false);for(inti0;in;i){if(outputed[i]false)// 找到一个未输出的顶点作为新分量的起点{vectorintcircle;// 存储当前分量的所有顶点编号circle.push_back(i);outputed[i]true;// 遍历所有其他未输出的顶点检查是否与 i 互相可达for(intj0;jn;j)if(outputed[j]falseedges[i][j]MAXNedges[j][i]MAXN){circle.push_back(j);outputed[j]true;}// 输出当前分量的所有名字用 , 分隔for(intj0;jcircle.size();j){if(j0)cout, ;coutnames[circle[j]];}cout\n;}}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),cout.sync_with_stdio(false);intcases0;// 数据集编号string name1,name2;while(cinnm,n0)// 当 n 和 m 均为 0 时结束{// 初始化邻接矩阵为无穷大不可达for(inti0;in;i)for(intj0;jn;j)edges[i][j]MAXN;// 重新初始化n 将用于记录实际出现的人数n0;indexer.clear();names.clear();// 读入 m 条通话记录for(inti1;im;i){cinname1name2;// 如果名字未出现过分配新编号if(indexer.find(name1)indexer.end()){indexer[name1]n;names[n]name1;n;}if(indexer.find(name2)indexer.end()){indexer[name2]n;names[n]name2;n;}// 添加有向边 name1 - name2权重设为 1表示可达edges[indexer[name1]][indexer[name2]]1;}// 输出空行分隔不同的数据集第一个数据集前不输出空行if(cases)cout\n;coutCalling circles for data set cases:\n;findAllCircles();}return0;}代码实现Kosaraju\texttt{Kosaraju}Kosaraju算法// Calling Circles// UVa ID: 247// Verdict: Accepted// Submission Date: 2017-10-20// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXV110;intvisited[MAXV],n,cscc;vectorlistintedges1(MAXV),edges2(MAXV);vectorintfn,scc;intm;mapstring,intindexer;mapint,stringnames;voiddfs(intu){visited[u]1;for(autov:edges1[u])if(!visited[v])dfs(v);fn.push_back(u);}voidreverseGraph(){for(intu1;un;u)for(autov:edges1[u])edges2[v].push_back(u);}voidrdfs(intu){visited[u]1;for(autov:edges2[u])if(!visited[v])rdfs(v);scc.push_back(u);}voidkosaraju(){fn.clear();memset(visited,0,sizeofvisited);for(intu1;un;u)if(!visited[u])dfs(u);reverseGraph();cscc0;memset(visited,0,sizeofvisited);while(fn.size()){intufn.back();if(!visited[u]){cscc,scc.clear();rdfs(u);for(inti0;iscc.size();i){if(i)cout, ;coutnames[scc[i]];}cout\n;}fn.pop_back();}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),cout.sync_with_stdio(false);intcases0;string name1,name2;while(cinnm,n0){for(intu1;un;u)edges1[u].clear(),edges2[u].clear();n0;indexer.clear(),names.clear();for(inti1;im;i){cinname1name2;if(indexer.find(name1)indexer.end()){indexer[name1]n;names[n]name1;}if(indexer.find(name2)indexer.end()){indexer[name2]n;names[n]name2;}edges1[indexer[name1]].push_back(indexer[name2]);}if(cases0)cout\n;coutCalling circles for data set cases:\n;kosaraju();}return0;}复杂度分析时间复杂度Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法为O(n3)O(n^3)O(n3)其中n≤25n \leq 25n≤25故最多约156251562515625次操作非常快。加上找分量的O(n2)O(n^2)O(n2)扫描总体可忽略不计。空间复杂度邻接矩阵大小为25×2562525 \times 25 62525×25625加上两个map\texttt{map}map存储最多252525个名字空间占用极小。总结本题是有向图中求强连通分量的经典应用。由于数据范围很小使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法求传递闭包然后根据互相可达的条件聚合顶点是一种简洁直观的做法。对于更大的图如n≤1000n \leq 1000n≤1000则需要使用Tarjan\texttt{Tarjan}Tarjan算法或Kosaraju\texttt{Kosaraju}Kosaraju算法但本题n≤25n \leq 25n≤25使得Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall成为最简单高效的解决方案。