秋招笔试

深信服笔试b卷第一题。判断网络是否联通。

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>

using namespace std;
int find(int n, vector<int>& parent) {
    if (parent[n] != n) {
        parent[n] = find(parent[n], parent);
    }
    return parent[n];
}
void unionSet(int a, int b, vector<int>& parent) {
    int rootX = find(a, parent);
    int rootY = find(b, parent);
    if (rootX != rootY) {
        parent[rootX] = rootY;
    }
}
int main() {
    int n, m;
    cin >> n >> m; 
    vector<int> parent(n+1,0);
    for (int i = 1; i < parent.size(); i++) {
        parent[i] = i;
    }
    map<string, int> ip;
    string tmp;
    int id;
    while (n--) {
        cin >> tmp >> id;
        ip[tmp] = id;

    }
   
    while (m--) {
        int a, b;
        cin >> a >> b;
        unionSet(a, b, parent);
    }
    int q;
    cin >> q;
    while (q--) {
        string s1, s2;
        cin >> s1 >> s2;
        int x = ip[s1];
        int y = ip[s2];
        if (find(x, parent) != find(y, parent))
        {
            cout << "No" << endl;
        }
        else {
            cout << "Yes" << endl;
        }
    }

}