请以C++源码解此题。本题目要求读入一个整数t,表示t个网络,然后是读入t组如下的数:3个整数N、n1和n2,n1行和n2行整数,最后输出t个count。 其中N表示节点个数,n1表示网络改变前的社区个数,n2表示网络改变后的社区个数,n1行整数分别表示网络改变前的n1个社区,n2行整数分别表示网络改变后的n2个社区,count是持续社区的个数(即未发生改变的社区个数)。1<=N<=100000000,1<=n1,n2<=100000 输入格式: t N n1 n2 id1_1 id1_2 id1_3 … id2_1 id2_2 id2_3 … ….. idn1_1 idn1_2 …. id1_1 id1_2 …. id2_1 id2_2 …. …. idn2_1 idn2_2 …. 输出格式: count_1 count_2 … count_t
时间: 2024-02-13 16:01:07 浏览: 112
以下是本题的 C++ 源码实现:
```c++
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
// 定义节点和社区
struct Node {
int id; // 节点编号
int community; // 社区编号
};
// 定义哈希函数,用于 unordered_set
struct NodeHash {
size_t operator()(const Node& node) const {
return hash<int>()(node.id);
}
};
// 计算未发生改变的社区数
int countUnchangedCommunities(int n, int n1, int n2, vector<vector<int>>& communities1, vector<vector<int>>& communities2) {
unordered_set<Node, NodeHash> set1; // 存储网络改变前的社区信息
for (int i = 0; i < n1; i++) {
for (int j = 0; j < communities1[i].size(); j++) {
Node node = {communities1[i][j], i};
set1.insert(node); // 将节点信息插入到哈希表中
}
}
int count = 0; // 统计未发生改变的社区数
for (int i = 0; i < n2; i++) {
for (int j = 0; j < communities2[i].size(); j++) {
Node node = {communities2[i][j], i};
if (set1.count(node) > 0) {
count++; // 如果当前节点在网络改变前的社区中,未发生改变的社区数加 1
}
}
}
return count;
}
int main() {
int t; // 网络个数
cin >> t;
while (t--) {
int n, n1, n2; // 节点数、n1和n2
cin >> n >> n1 >> n2;
vector<vector<int>> communities1(n1); // 存储网络改变前的社区信息
for (int i = 0; i < n1; i++) {
int k; // 当前社区中节点个数
cin >> k;
for (int j = 0; j < k; j++) {
int id; // 当前节点编号
cin >> id;
communities1[i].push_back(id);
}
}
vector<vector<int>> communities2(n2); // 存储网络改变后的社区信息
for (int i = 0; i < n2; i++) {
int k; // 当前社区中节点个数
cin >> k;
for (int j = 0; j < k; j++) {
int id; // 当前节点编号
cin >> id;
communities2[i].push_back(id);
}
}
int count = countUnchangedCommunities(n, n1, n2, communities1, communities2);
cout << count << " ";
}
return 0;
}
```
其中,`countUnchangedCommunities` 函数用于计算未发生改变的社区数。首先,将网络改变前的社区信息存储到一个哈希表 `set1` 中,其中哈希表的键为节点信息,值为当前节点所属的社区编号。接着,遍历网络改变后的社区信息,对于每个节点,如果其在 `set1` 中存在,说明其所属的社区未发生改变,未发生改变的社区数加 1。最后,将未发生改变的社区数作为函数返回值返回。
在主函数中,首先读入网络个数 `t`,然后在循环中读入每个网络的具体信息。接着,调用 `countUnchangedCommunities` 函数计算未发生改变的社区数,并输出到标准输出流中。
阅读全文