识别水果
题目描述:
在海上漂泊了249天后，由于食物和水都已消耗光了，三人已是筋疲力尽。终于，在第250天的早晨，一个隐隐约约的黑点在远处出现了，是一个小岛，三大护法高兴的几乎要跳起来。于是下令舰队全速前进，驶向小岛。
在登陆后，他们才知道，这就是著名的移花岛，岛上有三位女神：dp女神、涓涓女神和紫晶女神。由于三大女神与holy_one的关系不错，因此高兴地接待了他们三人。由于看到三人饥渴难耐，负责岛上水果的涓涓女神便带他们去了果园。
果园里水果丰富，共有n个，它们的标号为1~n，但有些水果是有毒，而且水果与水果之间有藤蔓相连，如果一个水果有毒，那么所有与它相连的所有水果都是有毒的。其中m个水果上面会贴着一个标签，从标签上可以看出这个水果是否有毒。当然，如果这个水果的标签显示无毒，但它与有毒的水果相连，那它也是有毒的。
为帮助三人尽快吃到水果，涓涓女神给了他们一张毒物字典，只有通过字典上的对应关系翻译后，才能知道水果是否有毒。转化后的名称中包含‘poison’，即表示这个水果有毒。
输入格式:
第一行，字符串a
第二行，字符串b
a串和b串长度都是26，a[i]到b[i]表示两个字母的对应关系。注意，对应关系是单向的。
两个整数n和m（m<=n<=10000）。
以下m行，每行第一个数是水果的标号k，后面是第k个水果的标签s，k和s之间有空格分隔开，标签长度小于255。
一个整数p。
以下p行，每行两个整数x,y 表示第x个水果和第y个水果之间有藤蔓相连。
输出格式:
无毒的水果的个数。
样例输入:
jgltnkyvhefdoszmcwqarixupb
ibtoupqadsxkcmrynhzegwljvf
10 6
6 awg
1 nij
3 ktjetcjip
7 nim
2 gqv
10 ktjetczfw
4
1 2
1 7
3 2
10 8
样例输出:
4
各位神犇，这道题目要用bfs还是dfs啊，总感觉是bfs的变种……传送门
我是用BFS的。。。
AC解题代码：
#include<bits/stdc++.h>
using namespace std;
map<char,char>b;
string s,s1,s2;
int n,m,p,x,sum,y,h[10001];
bool g[10001][10001];
queue<int>q;
void bfs()
{
while(!q.empty())
{
sum++;
int a=q.front();
q.pop();
for(int i=1;i<=n;i++)
{
if(g[a][i]==1&&h[i]==0)
{
h[i]=1;
q.push(i);
}
}
}
}
int main()
{
cin>>s1>>s2;
for(int i=0;i<26;i++)
{
b[s1[i]]=s2[i];
}
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>s;
for(int j=0;j<s.size();j++) s[j]=b[s[j]];//解密字符串
if(int(s.find("poison"))!=-1)//判断是否有毒
{
q.push(x);
h[x]=1;
}
}
cin>>p;
for(int i=1;i<=p;i++)
{
cin>>x>>y;
g[x][y]=g[y][x]=1;
}//保存图
bfs();//广搜
cout<<n-sum;
}
方案来自 梦想橡皮擦 狂飙组基于 GPT 编写的 “程秘”
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN = 10005;
int n, m, p, cnt;
int fa[MAXN];
bool poison[MAXN];
string a, b;
vector<int> G[MAXN];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) fa[fx] = fy;
}
int main() {
cin >> a >> b >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
merge(x, y);
}
cin >> p;
while (p--) {
int k;
string s;
cin >> k >> s;
for (char& c : s) c = b[a.find(c)];
if (s.find("poison") != string::npos) poison[find(k)] = true;
}
for (int i = 1; i <= n; i++) {
if (find(i) == i && !poison[i]) cnt++;
}
cout << cnt << endl;
return 0;
}