思路:首先处理名字,让字符串直接映射唯一一个数字,这就用map<string, int>即可。
然后,直接用并查集
#include<iostream> #include<map> #include<string> using namespace std; const int maxn = 2e4 + 10; map<string, int>mm; int fa[maxn]; int find(int x){ if (fa[x] == x)return x; return fa[x] = find(fa[x]); } int n, m; string name; string xx, yy; int main(){ cin >> n >> m; for (int i = 1; i <= n; ++i)fa[i] = i; for (int i = 1; i <= n; ++i) { cin >> name; mm[name] = i; } for (int i = 1; i <= m; ++i) { cin >> xx >> yy; int x = find(mm[xx]); int y = find(mm[yy]); if (x != y){ fa[x] = y; } } cin >> n; for (int i = 0; i < n; ++i) { cin >> xx >> yy;; int x = find(mm[xx]); int y = find(mm[yy]); if (x == y)cout << "Yes." << endl; else cout << "No." << endl; } }