解决思路
考虑到数据量不大(\(2 \le n \le 100, 2 \le m \le 100, 1 \le a_i \lt b_i \le n, 1 \lt c_i \le m)\)),因此可以用深度优先搜索
- 以颜色为第一优先级分类,分别将相连的 \(a_i, b_i\) 作标记
- 查询时,遍历所有颜色 \(c_i\),记录在当前颜色下,\(a_i\) 可以访问到的所有节点
- 根据记录结果查看目标节点 \(b_i\) 是否可以被访问到
#include <bits/stdc++.h>
int conn[101][101][101]{};
void dfs(int color, int node, std::vector<bool> &reach) {
reach[node] = true;
for (int i = 1; i <= 100; ++i) {
if (conn[color][node][i]) {
if (reach[i]) continue;
dfs(color, i, reach);
}
}
}
int main() {
int t;
t = 1;
while (t--) {
int n, m; std::cin >> n >> m;
for (int i = 0; i < m; ++i) {
int a, b, c; std::cin >> a >> b >> c;
conn[c][a][b] = 1;
conn[c][b][a] = 1;
}
int q; std::cin >> q;
while (q--) {
int ans = 0;
int u, v; std::cin >> u >> v;
for (int c = 1; c <= m; ++c) {
std::vector<bool> reach(101, false);
dfs(c, u, reach);
if (reach[v]) ++ans;
}
std::cout << ans << "\n";
}
}
return 0;
}