秋招笔试
深信服笔试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; } } }#深信服#