用C语言实现对给定的有向图删除若干条边。有向图中包含n个顶点,编号为0至n-1。 输入格式: 输入第一行为两个正整数n和e,分别表示图的顶点数和边数,其中n不超过20000,e不超过1000。接下来e行表示每条边的信息,每行为3个非负整数a、b、c,其中a和b表示该边的端点编号,c表示权值。各边并非按端点编号顺序排列。随后一行为一个整数k,表示删除的边的条数,接下来k行,每行为2个非负整数a、b,表示待删除的边为a->b。保证删除的边一定在原图中。 输出格式: 输出执行删边操作之后的图。每行表示一个顶点引出的所有边,格式为a:(a,b,w)……,表示有向边a->b的权值为w,a引出的多条边按编号b的递增序排列。若某顶点没有引出边,则不输出。 输入样例: 7 7 0 1 5 0 3 7 0 6 6 1 2 4 2 5 1 3 5 3 6 5 4 2 2 5 0 1 输出样例: 0:(0,3,7)(0,6,6) 1:(1,2,4) 3:(3,5,3) 6:(6,5,4)
时间: 2023-02-08 18:39:50 浏览: 321
C语言实现对给定的有向图删除若干条边的代码如下:
```C
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
const int N = 2e4 + 10;
int n, e, k;
unordered_map<int, vector<pair<int, int>>> g;
int main() {
cin >> n >> e;
for (int i = 0; i < e; i++) {
int a, b, c;
cin >> a >> b >> c;
g[a].push_back({b, c});
}
cin >> k;
for (int i = 0; i < k; i++) {
int a, b;
cin >> a >> b;
vector<pair<int, int>> &edges = g[a];
for (int j = 0; j < edges.size(); j++) {
if (edges[j].first == b) {
edges.erase(edges.begin() + j);
break;
}
}
}
for (auto &[u, edges] : g) {
if (edges.size() == 0) continue;
cout << u << ":";
sort(edges.begin(), edges.end(), [](auto &a, auto &b) {
return a.first < b.first;
});
for (auto &[v, w] : edges) {
cout << "(" << u << "," << v << "," << w << ")";
}
cout << endl;
}
return 0;
}
```
该代码使用了unordered_map来存储有向图,读入时先存储所有边,之后再删除指定的边,最后按照题目要求输出。
阅读全文