-----------------------
题目链接:MIKU
---------------------
我现在发现找BUG的最好方法————喝水
喝一次找一个,喝两次A道题
---------------------------
好,下面来分析这道题,这道题一看,大家一定就会想到并查集
(不知道并查集是什么?)请自行百度或者是看博客:(链接指向网址未完工)
但是,并查集我们是针对数的,而这道题都是字符串,怎么办呢?就是建立一个结构体来储存名字和编号,当然,这样在查询时就必须要遍历每一个数组才能拿到编号,不过对于这套题来说,复杂度足够了。
所以说这道题还是挺模板的
或许MAP对于这道题也可以用,但是对于像我这样的蒟蒻来说,这种结构体还是比较稳定的;
(或许可以用一个<string,string>的MAP?,我没试)
---------------------------
再说一句,这道题的数据很水,写的是20000但是我开了个10000的数组就够了】
---------------------------
/* 我现在发现了怎样A题 喝一口水找出一个bug 啊啊啊啊 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct com{
int no;
string name;
} fa[];//受题目影响,就用了结构体
//用结构体打包
int faa[];//并查集部分
int n,m,k;
//得到名字,但是我们的并查集是要处理编号,所以说我们就要
//遍历得到编号
int find(string x){
for(int i=;i<=n+;++i)
if(fa[i].name==x)
return fa[i].no;
}
int findd(int x)//并查集部分
{
if(faa[x]==x)
return x;
else
return faa[x]=findd(faa[x]);
} string s,s1;
int main()
{
cin>>n>>m;//读入部分
for(int i=;i<=n;++i)
{
cin>>s;
fa[i].no=i;
fa[i].name=s;//记录名字与编号
faa[i]=i;//并查集部分
}
for(int i=;i<=m;++i)
{
cin>>s>>s1;
int v1=find(s);
int v2=find(s1);//将我们得到的名字转化成编号
// cout<<v1<<" "<<v2<<endl;
if(findd(v1)!=findd(v2))
faa[findd(v1)]=findd(v2);//并查集部分
}
cin>>k;
for(int i=;i<=k;++i)
{
cin>>s>>s1;
if(findd(find(s1))==findd(find(s)))//转换成编号,并查集部分
cout<<"Yes."<<endl;//输出
else
cout<<"No."<<endl;
}
return ;
}
AC
--------------------------
May MIKU be with you.
--------------