题目描述:
在海上漂泊了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
#include <bits/stdc++.h>
using namespace std;
string s,s1,s2;
bool a[10001][10001]; //存储一个图,a[i][j] =1,表示第i个水果和第j个水果是有直接相连
int n,m,n1,n2,m1,m2,ans;
unordered_map<char,char> maps;
unordered_set< int > b;//集合,每个元素只储存一个
queue<int> q;
int main(){
cin>>s1>>s2;
for(int i=0; i<s1.size(); i++){
maps[s1[i]]=s2[i];
}
cin>>n>>m;
for(int i=1; i<=m; i++){
cin>>n1>>s;
if(s.size()<6) continue; //继续下一次循环,不是跳出循环,跳出是break
for( auto &j : s ){//新版本的功能,C++11
j = maps[j];
}
if(int (s.find("poison")) != -1){
q.push(n1); //把有毒的水果,放入队列
b.insert( n1 );
}
}
cin>>n2;
while(n2>0){
scanf("%d %d", &m1, &m2);
a[m1][m2]=a[m2][m1]=1;
n2--;
}
//=============================BFS
while( !q.empty() ){
int x=q.front();
ans++;
for(int i=1; i<=n; i++){ //枚举所有的水果编号
if( a[x][i] && b.count(i) == 0 ){ //b.find( i ) == b.end()
q.push(i);
b.insert( i );
}
}
q.pop();
}
cout << n-ans;
}