2024/2/7 图的基础知识

图的存储

B3643 图的存储 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：mp[n][n]用来存邻接矩阵，二维vector用来存每个点连的点

完整代码：

#include <bits/stdc++.h>
#define int long long
const int N = 1e5 + 10;
int n, m;
std::vector<std::vector<int>> g(N);
signed main() {std::cin >> n >> m;int mp[n + 10][n + 10];memset(mp, 0, sizeof(mp));for (int i = 0; i < m; i++) {int u, v;std::cin >> u >> v;g[u].push_back(v);//里面装的是u能到的点，u能到vg[v].push_back(u);//v能到ump[u][v] = 1;mp[v][u] = 1;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {std::cout << mp[i][j] << " ";}std::cout << "\n";}for (int i = 1; i <= n; i++) {std::sort(g[i].begin(), g[i].end());}for (int i = 1; i <= n; i++) {std::cout << g[i].size() << " ";for (int j = 0; j < g[i].size(); j++) {std::cout << g[i][j] << " ";}std::cout << "\n";}return 0;
}

图的遍历

P3916 图的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：反向建图，用dfs确定每一个点最大可以到达哪一个点，然后按顺序输出

完整代码：

#include <bits/stdc++.h>
#define int long long
const int N = 1e5 + 10;
std::vector<std::vector<int>> g(N);
int vis[N];
void dfs(int x, int y) {if (vis[x] != 0)return;else {vis[x] = y;for (int i = 0; i < g[x].size(); i++) {dfs(g[x][i], y);}}
}
signed main() {int n, m;std::cin >> n >> m;for (int i = 1; i <= m; i++) {int u, v;std::cin >> u >> v;g[v].push_back(u);}for (int i = n; i >= 1; i--) {dfs(i, i);}for (int i = 1; i <= n; i++) {std::cout << vis[i] << " ";}return 0;
}