题目描述题目要求计算给定无向图中极大连通子图即连通分量的数量。图的节点由大写字母表示输入给出最大节点名称即节点集合为A\texttt{A}A到该字符以及若干条边。需要输出连通分量的个数。输入格式第一行一个整数NNN表示测试用例的数量后面跟一个空行。每个测试用例的第一行是一个大写字母表示最大节点名称例如E表示节点为A,B,C,D,E\texttt{A,B,C,D,E}A,B,C,D,E。接下来若干行每行两个大写字母表示一条边。输入以空行结束。两个连续测试用例之间由一个空行分隔。输出格式对于每个测试用例输出一行一个整数表示连通分量的个数。两个连续测试用例的输出之间由一个空行分隔。样例输入1 E AB CE DB EC输出2题目分析本题的核心是计算无向图的连通分量数量。可以使用并查集Union-Find\texttt{Union-Find}Union-Find高效求解。并查集实现初始化每个节点自成一集合父节点指向自身。对于每条边(u,v)(u, v)(u,v)将uuu和vvv所在的集合合并。最终统计有多少个节点是其所在集合的代表元即parent[i] i即为连通分量数。节点范围节点从A\texttt{A}A开始到输入的最大字母结束。例如最大字母为E则节点为A,B,C,D,E\texttt{A,B,C,D,E}A,B,C,D,E共555个。不需要考虑不在该范围内的其他字母。输入处理第一行是最大节点名称如E需要记录该字符并转换为索引。后续行每行两个大写字母表示一条边可能有多余空格但每行只包含两个字母。输入以空行结束需要正确读取。复杂度分析并查集操作近似常数总复杂度O(边数×α(N))O(\text{边数} \times \alpha(N))O(边数×α(N))其中N≤26N \le 26N≤26。代码实现// Graph Connectivity// UVa ID: 459// Verdict: Accepted// Submission Date: 016-07-15// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intparent[26],ranks[26];voidmakeSet(){for(inti0;i26;i){parent[i]i;ranks[i]0;}}// 带路径压缩的查找使用递归实现。intfindSet(intx){return(xparent[x]?x:parent[x]findSet(parent[x]));}// 集合的按秩合并。voidunionSet(intx,inty){xfindSet(x);yfindSet(y);if(xy)return;if(ranks[x]ranks[y])parent[y]x;else{parent[x]y;if(ranks[x]ranks[y])ranks[y];}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases;cincases;cin.ignore(1024,\n);string line;getline(cin,line);for(inti1;icases;i){if(i1)coutendl;makeSet();intmaxIndex0;while(getline(cin,line),line.length()0){if(line.length()1){maxIndexline.front()-A;continue;}for(inti1;iline.length();i)unionSet(line[i]-A,line.front()-A);}intcounter0;for(inti0;imaxIndex;i)if(parent[i]i)counter;coutcounterendl;}return0;}