题库 C++/C语言题库 题目列表 给定两个无向图G1和G2 ,判断它们是否同构。图的同构...
单选题

给定两个无向图

G1G2 ,判断它们是否同构。图的同构是指两个图的节点可以通过某种重新编号的方式完全匹配,且边的连接关系一致。 

为了简化问题,假设图的节点编号从0n-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 }


A.
hash += to_string(neighbor);
B.
hash += to_string(neighbors);
C.
hash += to_string(neighbor) + ",";
D.
hash -= to_string(neighbors);
题目信息
2025年 七级 选择题
-
正确率
0
评论
34
点击