2025-11-08 16:22:55
发布于：江苏
2阅读
0回复
0点赞
1. 文献阅读
#include <bits/stdc++.h>
using namespace std;
int g[1005][1005];
int n, m;
bool vis[1005];
void dfs(int x){
vis[x] = 1; //标记当前点
cout << x << ' ';
for (int i=1; i<=n; i++){
if (vis[i] == 0 && g[x][i]==1){
dfs(i);
}
}
}
queue<int> q;
void bfs(int x){
q.push(x);
vis[x] = 1; //标记当前走过的点
while (q.size()){
int t = q.front();//访问第一个元素
q.pop();
cout << t << " ";
for (int i=1; i<=n; i++){
if (vis[i]==0 && g[t][i] == 1){
q.push(i);
vis[i] = 1;
}
}
}
}
int main(){
int x, y;
cin >> n >>m;
for (int i=1; i<=m; i++){
//邻接矩阵存图
cin >> x >> y;
g[x][y] = 1;
}
dfs(1);
memset(vis, 0, sizeof(vis));
cout << endl;
bfs(1);
return 0;
}
/*
8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8
*/
2. 图的遍历
#include <bits/stdc++.h>
using namespace std;
int g[1005][1005];
int n, m;
bool vis[1005];
int ans[1005]; //记录答案
void dfs(int begin, int x){//x表示当前搜索点
ans[begin] = max(x, ans[begin]);
vis[x] = 1;
for (int i=1; i<=n; i++){
if (vis[i]==0 && g[x][i]==1){
dfs(begin, i);
}
}
}
int main(){
cin >> n >> m;
for (int i=1; i<=m; i++){
int x, y;
cin >> x>> y;
g[x][y] = 1;
}
for(int i=1; i<=n; i++){
memset(vis, 0, sizeof vis);
dfs(i, i);
}
for(int i=1; i<=n; i++){
cout << ans[i] << ' ';
}
return 0;
}
/*
[图的遍历]
题目描述
给出 N 个点，M 条边的有向图，对于每个点 v，求 A(v) 表示从点 v 出发，能到达的编号最大的点。
输入格式
第1行2个整数N,M(1≤N≤10
样例组
输入#1
4 3
1 2
2 4
4 3
输出#1
4 4 3 4
*/
3. 小马聚餐
这里空空如也
有帮助，赞一个