题解 UVA793 【Network Connections】

把两个点联通，查询两个点是否联通，显然可以用[并查集](https://www.luogu.com.cn/blog/My-luoguBuoke-HZR/solution-p3367)维护。 但是，这题没有这么简单，输入输出很坑。简单地列一下需要注意的点吧： - 数据组数 $T$ 后有一个空行； - 每组数据以一个空行或 `EOF` 为结束标志； - 输出最后一组数据时必须只输出一个换行。 那怎么应对这些坑呢？我们来学习一下两个函数： - [`fgets`](https://zh.cppreference.com/w/cpp/io/c/fgets) - 说明：输入一整行的所有字符，与 `getline` 类似，需要注意输入的字符串后有一个换行。如果输入成功了，返回一个 `char*`，否则返回 `NULL`。 - 用法：`fgets(a,极大值,stdin)`，其中 `a` 是 `char[]` 类型。 - 例子：`fgets(a,1010,stdin)`。 - [`sscanf`](https://zh.cppreference.com/w/cpp/io/c/fscanf) - 说明：从给定的字符串中按给定格式输入数据。 - 用法：`sscanf(a,格式串,...)`，其中 `a` 是 `char[]` 类型。 - 例子： ```cpp char a[]="c 1 2"; char op; int x,y; sscanf(a,"%c%d%d",&op,&x,&y); printf("op='%c',x=%d,y=%d",op,x,y); ``` 输出 `op='c',x=1,y=2`。 好了，这道题很简单了，具体实现方法看代码吧： ```cpp #include <cstdio> #include <iostream> using namespace std; template<int N> struct Union_set{//并查集 int fa[N+10]; Union_set(){for(int i=1;i<=N;i++) fa[i]=i;}//初始化 int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}//找祖先 void merge(int x,int y){fa[find(x)]=find(y);}//联通 bool query(int x,int y){return find(x)==find(y);}//询问是否联通 }; int T; Union_set<10010> s; char a[1010]; int mian(){ scanf("%*d\n");//%*d 表示读取这个数但不存下来，这个数是 n，它是废物 //记得顺手把这一行的换行吃掉 int ans[2]={0,0}; s=Union_set<10010>();//如果封装了就可以这样初始化 while(fgets(a,1010,stdin)&&a[0]!='\n'){ // 判 EOF 判空行 char op;int x,y; sscanf(a,"%c%d%d",&op,&x,&y); if(op=='c') s.merge(x,y); else ans[s.query(x,y)]++; } printf("%d,%d\n",ans[1],ans[0]); if(T) printf("\n");//注意神仙格式 return 0; } int main(){ scanf("%d\n\n",&T);//吃掉两个换行 while(T--) mian(); return 0; } ``` Q：为什么不直接使用 `scanf` 输入呢？ A：一组数据结束后，继续读入会把下一组数据损坏。