图的存储三 题目描述 给定n个节点,m条边的有向图,询问图中的一条边,回答出这条边的开始结点和终点结点。
时间: 2024-06-08 09:12:20 浏览: 281
这道题可以使用邻接表来存储图,对于每次询问,直接在邻接表中查找即可。
具体实现可以先输入n和m,然后使用一个vector数组来存储每个节点的出边,vector数组的下标表示节点编号,vector中存储的是该节点的出边所连接的节点编号。接下来输入每次询问的边,对于每次询问,直接在起始节点的vector中查找目标节点即可。
下面是C++的示例代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
// 邻接表存储图
vector<int> adj[n+1];
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
// 处理询问
int q;
cin >> q;
while (q--) {
int u, v;
cin >> u >> v;
bool found = false;
for (int i = 0; i < adj[u].size(); i++) {
if (adj[u][i] == v) {
found = true;
break;
}
}
if (found) {
cout << u << " " << v << endl;
} else {
cout << "No edge found." << endl;
}
}
return 0;
}
```
阅读全文