1 条题解
-
0
用vector存图,把每个vector排序,然后依次进行DFS和BFS即可。
参考代码
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int n, m, x, y; vector<int> g[MAXN]; queue<int> que; bool vis[MAXN]; void dfs(int u) { vis[u] = true; cout << u << " "; for (int i = 0; i < g[u].size(); i++) if (!vis[g[u][i]]) dfs(g[u][i]); } void bfs(int u) { vis[u] = true; que.push(u); while (!que.empty()) { int x = que.front(); que.pop(); cout << x << " "; for (int i = 0; i < g[x].size(); i++) { if (!vis[g[x][i]]) { vis[g[x][i]] = true; que.push(g[x][i]); } } } } int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> x >> y; g[x].push_back(y); } for (int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end()); dfs(1); cout << endl; memset(vis, false, sizeof(vis)); bfs(1); return 0; }
- 1
信息
- ID
- 896
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- (无)
- 递交数
- 20
- 已通过
- 13
- 上传者