复兴提高班第十七课 图的遍历
2025-10-18 20:29:30
发布于：上海
0阅读
0回复
0点赞
T1公路查询
//vector数组
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
struct node {
int v, w;
};
vector<node> ve[maxn];
int main() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
ve[u].push_back({ v,w });
}
while (q--) {
int x;
cin >> x;
for (int i = (int)ve[x].size() - 1; i >= 0; i--) {
cout << ve[x][i].v << " " << ve[x][i].w << '\n';
}
}
return 0;
}
//链式前向星
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct node {
int to; // 终点
int next; // 下一个位置
int w; // 权重
} edge[N]; // 边结构体数组
int head[N]; // 链表数组，顶点链表起始位置
int cnt; // 当前的已加入的边数
// 插入一条新边，起点为 u
void add(int u, int v, int w) {
// 表示新边的结点
edge[++cnt].to = v;
edge[cnt].w = w;
// 新结点指向 u 的链表的链头
edge[cnt].next = head[u];
// 新结点作为新的链头
head[u] = cnt;
}
int main() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w); // 添加边
}
while (q--) {
int x;
cin >> x;
for (int j = head[x]; j; j = edge[j].next) {
cout << edge[j].to << " " << edge[j].w << '\n';
}
}
return 0;
}
T2【图的存储】有向图的权重
//vector数组
#include<bits/stdc++.h>
using namespace std;
struct node {
int v, w;
};
vector<node> ve[109];
int main() {
int n, m;
cin >> n >> m;
while (m--) {
int u, v, w;
cin >> u >> v >> w;
ve[u].push_back({ v,w });
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < ve[i].size(); j++) {
ans += ve[i][j].w;
}
}
cout << ans;
return 0;
}
//链式前向星
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct node {
int to; // 终点
int next; // 下一个位置
int w; // 权重
} edge[N]; // 边结构体数组
int head[N]; // 链表数组，顶点链表起始位置
int cnt; // 当前的已加入的边数
// 插入一条新边，起点为 u
void add(int u, int v, int w) {
// 表示新边的结点
edge[++cnt].to = v;
edge[cnt].w = w;
// 新结点指向 u 的链表的链头
edge[cnt].next = head[u];
// 新结点作为新的链头
head[u] = cnt;
}
int main() {
int n, m;
cin >> n >> m;
while (m--) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w); // 添加边
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = head[i]; j; j = edge[j].next) {
ans += edge[j].w;
}
}
cout << ans;
return 0;
}
T3【图的存储】点的个数
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
vector<int> ve[maxn];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
ve[u].push_back(v);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (ve[i].size() <= 3) ans++;
}
cout << ans;
return 0;
}
T4【图的存储】公路查询2
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
struct node {
int v, w;
};
bool cmp(node A, node B) {
if (A.v != B.v) return A.v < B.v;
return A.w < B.w;
}
vector<node> ve[maxn];
int main() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < m; i++) {
int x, y, len;
cin >> x >> y >> len;
ve[x].push_back({ y,len });
}
for (int i = 1; i <= n; i++) sort(ve[i].begin(), ve[i].end(), cmp);
while (q--) {
int x;
cin >> x;
for (int i = 0; i < ve[x].size(); i++) {
int j = i;
while (j < ve[x].size() && ve[x][j].v == ve[x][i].v)j++;
cout << ve[x][i].v << " " << ve[x][i].w << '\n';
i = j - 1;
}
}
return 0;
}
T5H朋友圈的数量
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 9;
vector<int> ve[maxn];
bool vis[maxn];
void bfs(int x) {
queue<int> q;
q.push(x);
vis[x] = 1;
while (q.size()) {
int r = q.front();
q.pop();
for (int i = 0; i < ve[r].size(); i++){
int y = ve[r][i];
if (!vis[y]) {
vis[y] = 1;
q.push(y);
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
ve[u].push_back(v);
ve[v].push_back(u);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
bfs(i);
ans++;
}
}
cout << ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 9;
vector<int> ve[maxn];
bool vis[maxn];
void dfs(int x) {
vis[x] = 1;
for (int i = 0; i < ve[x].size(); i++) {
int y = ve[x][i];
if (vis[y]) continue;
dfs(y);
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
ve[u].push_back(v);
ve[v].push_back(u);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
dfs(i);
ans++;
}
}
cout << ans;
return 0;
}
T6图的遍历
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
vector<int> ve[maxn];
int ans[maxn];
void bfs(int x) {
ans[x] = x;
queue<int> q;
q.push(x);
while (q.size()) {
int r = q.front();
q.pop();
for (int i = 0; i < ve[r].size(); i++) {
int y = ve[r][i];
if (!ans[y]) {
ans[y] = x;
q.push(y);
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
ve[v].push_back(u);
}
for (int i = n; i >= 1; i--) {
if (!ans[i]) {
bfs(i);
}
}
for (int i = 1; i <= n; i++)
cout << ans[i] << " ";
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
vector<int> ve[maxn];
int ans[maxn], vis[maxn];
void dfs(int x, int ma) {
vis[x] = 1;
ans[x] = ma;
for (int i = 0; i < ve[x].size(); i++) {
int y = ve[x][i];
if (vis[y]) continue;
dfs(y, ma);
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
ve[v].push_back(u);
}
for (int i = n; i >= 1; i--) {
if (!vis[i]) dfs(i, i);
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << " ";
}
return 0;
}
这里空空如也
有帮助，赞一个