题解 UVA793 【Network Connections】

_caiji_ · 2021-07-15 11:39:02 · 题解

把两个点联通，查询两个点是否联通，显然可以用并查集维护。

但是，这题没有这么简单，输入输出很坑。简单地列一下需要注意的点吧：

• 数据组数 T 后有一个空行；
• 每组数据以一个空行或 EOF 为结束标志；
• 输出最后一组数据时必须只输出一个换行。

那怎么应对这些坑呢？我们来学习一下两个函数：

• fgets
  • 说明：输入一整行的所有字符，与 getline 类似，需要注意输入的字符串后有一个换行。如果输入成功了，返回一个 char*，否则返回 NULL。
  • 用法：fgets(a,极大值,stdin)，其中 a 是 char[] 类型。
  • 例子：fgets(a,1010,stdin)。
• sscanf
  • 说明：从给定的字符串中按给定格式输入数据。
  • 用法：sscanf(a,格式串,...)，其中 a 是 char[] 类型。
  • 例子：

    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。

好了，这道题很简单了，具体实现方法看代码吧：

#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：一组数据结束后，继续读入会把下一组数据损坏。