题目描述Bob\texttt{Bob}Bob是网络管理员负责监督计算机网络。他记录网络中计算机之间的连接日志每条连接是双向的。两台计算机相连若它们直接相连或通过其他计算机间接相连。偶尔Bob\texttt{Bob}Bob需要快速判断给定两台计算机是否连通。给定若干条连接操作c i j和查询操作q i j连接操作将计算机iii和jjj连接查询操作询问iii和jjj当前是否连通。要求统计所有查询中成功连通和失败不连通的数量。输入格式第一行为一个正整数表示测试用例个数。随后有一个空行。每个测试用例的第一行为一个正整数nnn表示计算机数量编号111到nnn。随后若干行每行以字符c或q开头后跟两个整数i,ji, ji,j表示连接或查询操作。输入可能包含空行操作行可能以任意顺序出现。每个测试用例的输入以文件结束或遇到非c/q字符结束实际通常以空行结束。输出格式对于每个测试用例输出一行包含两个整数用逗号分隔成功查询数和失败查询数。不同测试用例输出之间用一个空行分隔。样例输入2 10 c 1 5 c 2 7 q 7 1 c 3 9 q 9 6 c 2 5 q 7 5 1 q 1 1 c 1 1 q 1 1样例输出1,2 2,0题目分析本题是典型的动态连通性问题支持添加边和查询连通性。使用并查集Union-Find\texttt{Union-Find}Union-Find数据结构可高效处理。对于每个测试用例初始化nnn个独立集合。对每行输入若为c则合并iii和jjj若为q则检查iii和jjj是否在同一个集合中若相同则成功数加111否则失败数加111。最后输出成功和失败数量。解题思路实现步骤确定如下步骤1\texttt{1}1. 读入测试用例个数casescasescases忽略空行。步骤2\texttt{2}2. 对于每个测试用例读入nnn初始化并查集每个节点自成一集合。步骤3\texttt{3}3. 循环读取行每次先读入一个字符opopop。若opopop为c则读入两个整数i,ji, ji,j合并iii和jjj若opopop为q则读入i,ji, ji,j若find(i)find(j)\texttt{find}(i) \texttt{find}(j)find(i)find(j)则成功数加111否则失败数加111。若opopop既不是c也不是 q$则将该字符放回输入流并跳出循环通常表示空行或文件结束。步骤4\texttt{4}4. 输出当前用例的成功数和失败数以逗号分隔。若还有后续用例输出一个空行。并查集采用路径压缩和按秩合并使查询和合并操作近似常数时间。代码实现// Network Connections// UVa ID: 793// Verdict: Accepted// Submission Date: 2016-11-29// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAX_N10010;intparent[MAX_N],ranks[MAX_N];voidmakeSet(){for(inti0;iMAX_N;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;for(intc1;ccases;c){if(c1)cout\n;intn;cinn;makeSet();charform_of_pair;inti,j,success0,failed0;while(cinform_of_pair){if(form_of_pairc||form_of_pairq){cinij;if(form_of_pairc){if(findSet(i)!findSet(j))unionSet(i,j);}else{if(findSet(i)findSet(j))success;elsefailed;}}else{cin.putback(form_of_pair);break;}}coutsuccess,failed\n;}return0;}总结本题通过并查集高效维护动态连通性支持合并和查询操作。使用路径压缩和按秩合并可保证操作接近常数时间适用于较大规模数据。输入处理需注意可能出现的空行和非操作字符通过cin.putback实现回溯。输出格式要求逗号分隔且不同用例间有空行。该解法简洁高效是并查集在连通性问题中的经典应用。