posted on 2021-07-15 11:39:02 | under 题解 | source
把两个点联通,查询两个点是否联通,显然可以用并查集维护。
但是,这题没有这么简单,输入输出很坑。简单地列一下需要注意的点吧:
- 数据组数 \(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:一组数据结束后,继续读入会把下一组数据损坏。
原文地址:http://www.cnblogs.com/caijianhong/p/solution-UVA793.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性