1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <bits/stdc++.h>
using namespace std;
const int LEN = 1e6 + 50;
int n, m;
vector<int> e[LEN];
bool vis[LEN];
queue<int> q;
struct edge {
int x_, y_;
} arr[LEN];
void init() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
cin >> arr[i].x_ >> arr[i].y_;
}
sort(arr + 1, arr + 1 + m, [](edge &a, edge &b) -> bool {
if (a.x_ != b.x_) return a.x_ < b.x_;
return a.y_ < b.y_;
});
for (int i = 1; i <= m; ++i) {
e[arr[i].x_].emplace_back(arr[i].y_);
}
}
void dfs(int x) {
if (vis[x]) return;
vis[x] = true;
cout << x << " ";
for (int i = 0, sz = e[x].size(); i < sz; ++i) {
dfs(e[x][i]);
}
}
void bfs() {
vis[1] = true;
q.emplace(1);
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
for (int i = 0, sz = e[u].size(); i < sz; ++i) {
if (vis[e[u][i]]) continue;
vis[e[u][i]] = true;
q.emplace(e[u][i]);
}
}
}
int main() {
init();
dfs(1);
memset(vis, 0, sizeof(vis));
cout << endl;
bfs();
return 0;
}
|