校運(yùn)會(huì)C++
題目描述
假設(shè)一共有?N（2≤N≤2×104）個(gè)參賽選手。
老師會(huì)告訴你這?N?個(gè)選手的名字。
接著會(huì)告訴你?M（1≤M≤106）句話，即告訴你學(xué)生 A 與學(xué)生 B 在同一個(gè)組里。
如果學(xué)生 A 與學(xué)生 B 在同一組里，學(xué)生 B 與學(xué)生 C 也在同一組里，就說明學(xué)生 A 與學(xué)生 C 在同一組。
然后老師會(huì)問你?1≤K≤106）句話，即學(xué)生 X 和學(xué)生 Y 是否在同一組里。
若是則輸出?Yes.，否則輸出?No.
輸入
第一行輸入?N?和?M。
接下來?N?行輸入每一個(gè)同學(xué)的名字。
再往下?M?行每行輸入兩個(gè)名字，且保證這兩個(gè)名字都在上面的?N?行中出現(xiàn)過，表示這兩個(gè)參賽選手在同一個(gè)組里。
再來輸入?K。
接下來輸入?K?個(gè)體育老師的詢問。
輸出
對(duì)于每一個(gè)體育老師的詢問，輸出?Yes.?或?No.
樣例輸入?復(fù)制
10 6
Jack
Mike
ASDA
Michel
brabrabra
HeHe
HeHE
papapa
HeY
Obama
Jack Obama
HeHe HeHE
brabrabra HeHe
Obama ASDA
papapa Obama
Obama HeHE
3
Mike Obama
HeHE Jack
papapa brabrabra
樣例輸出?復(fù)制
No.
Yes.
Yes.
程序
#include<bits/stdc++.h>using namespace std;int n,m,k;string f[20001],mz[20001];int fname(string name){????for (int i=1;i<=n;i++){????????if (name==mz[i]) return i;????}}string find(string name){????if (f[fname(name)]==name) return name;????return f[fname(name)]=find(f[fname(name)]);} int main(){????scanf("%d %d",&n,&m);????for (int i=1;i<=n;i++){????????cin>>f[i];????????mz[i]=f[i];????}????for (int i=1;i<=m;i++){????????string a,b;????????cin>>a>>b;????????f[fname(find(a))]=find(b);????}????scanf("%d",&k);????for (int i=1;i<=k;i++){????????string a,b;????????cin>>a>>b;????????if (find(a)==find(b)) printf("Yes.\n");????????else printf("No.\n");????}????return 0;}標(biāo)簽：
