给定两个无向图
G1和G2 ,判断它们是否同构。图的同构是指两个图的节点可以通过某种重新编号的方式完全匹配,且边的连接关系一致。
为了简化问题,假设图的节点编号从0到n-1,并且图的边以邻接表的形式给出。下面程序中横线处应该给出的是 ()
1 #include <iostream> 2 #include <vector> 3 #include <map> 4 #include <algorithm> 5 using namespace std; 6 7 string graphHash(vector<vector<int>>& graph) { 8 vector<string> nodeHashes(graph.size()); 9 for (int i = 0; i < graph.size(); i++) { 10 vector<int> neighbors = graph[i]; 11 sort(neighbors.begin(), neighbors.end()); 12 string hash; 13 for (int neighbor : neighbors) { 14 —————————————————————————— 15 } 16 nodeHashes[i] = hash; 17 } 18 sort(nodeHashes.begin(), nodeHashes.end()); 19 string finalHash; 20 for (string h : nodeHashes) { 21 finalHash += h + ";"; 22 } 23 return finalHash; 24 } 25 26 int main() { 27 int n; 28 cin >> n; 29 30 vector<vector<int>> G1(n); 31 for (int i = 0; i < n; i++) { 32 int k; 33 while (cin >> k) { 34 G1[i].push_back(k); 35 if (cin.get() == '\n') break; 36 } 37 } 38 39 vector<vector<int>> G2(n); 40 for (int i = 0; i < n; i++) { 41 int k; 42 while (cin >> k) { 43 G2[i].push_back(k); 44 if (cin.get() == '\n') break; 45 } 46 } 47 48 string hash1 = graphHash(G1); 49 string hash2 = graphHash(G2); 50 51 if (hash1 == hash2) { 52 cout << "YES" << endl; 53 } else { 54 cout << "NO" << endl; 55 } 56 57 return 0; 58 }
hash += to_string(neighbor);
hash += to_string(neighbors);
hash += to_string(neighbor) + ",";
hash -= to_string(neighbors);