企业官网建设流程全解析

题目描述

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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAX_N=10010;intparent[MAX_N],ranks[MAX_N];voidmakeSet(){for(inti=0;i<MAX_N;i++){parent[i]=i;ranks[i]=0;}}// 带路径压缩的查找，使用递归实现。intfindSet(intx){return(x==parent[x]?x:parent[x]=findSet(parent[x]));}// 集合的按秩合并。voidunionSet(intx,inty){x=findSet(x);y=findSet(y);if(x==y)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;cin>>cases;for(intc=1;c<=cases;c++){if(c>1)cout<<'\n';intn;cin>>n;makeSet();charform_of_pair;inti,j,success=0,failed=0;while(cin>>form_of_pair){if(form_of_pair=='c'||form_of_pair=='q'){cin>>i>>j;if(form_of_pair=='c'){if(findSet(i)!=findSet(j))unionSet(i,j);}else{if(findSet(i)==findSet(j))success++;elsefailed++;}}else{cin.putback(form_of_pair);break;}}cout<<success<<','<<failed<<'\n';}return0;}

总结

本题通过并查集高效维护动态连通性，支持合并和查询操作。使用路径压缩和按秩合并可保证操作接近常数时间，适用于较大规模数据。输入处理需注意可能出现的空行和非操作字符，通过cin.putback实现回溯。输出格式要求逗号分隔，且不同用例间有空行。该解法简洁高效，是并查集在连通性问题中的经典应用。