52 lines
948 B
C++
52 lines
948 B
C++
#include <iostream>
|
|
#include <algorithm>
|
|
#include <vector>
|
|
#include <deque>
|
|
using namespace std;
|
|
vector<vector<int>> adj;
|
|
vector<bool> used;
|
|
//
|
|
void dfs(int idx){
|
|
if(used[idx]) return;
|
|
used[idx] = true; // 标记已访问
|
|
cout << idx + 1 << " ";
|
|
|
|
for(auto x : adj[idx]){
|
|
dfs(x);
|
|
}
|
|
}
|
|
|
|
int main(){
|
|
int v, e;
|
|
cin >> v >> e;
|
|
adj.resize(v);
|
|
used.resize(v, false);
|
|
for(int i = 0; i < e; i++){
|
|
int a, b;
|
|
cin >> a >> b;
|
|
adj[a - 1].push_back(b - 1);
|
|
}
|
|
for(int i = 0; i < v; i++){
|
|
sort(adj[i].begin(), adj[i].end());
|
|
}
|
|
dfs(0);
|
|
fill(used.begin(), used.end(), false);
|
|
|
|
cout << endl;
|
|
//bfs
|
|
deque<int> q;
|
|
q.push_back(0);
|
|
used[0] = true;
|
|
while(!q.empty()){
|
|
int top = q.front(); q.pop_front(); // 注意这里用 front()
|
|
cout << top + 1 << " ";
|
|
for(auto x : adj[top]){
|
|
if(!used[x]){
|
|
used[x] = true; // 标记访问
|
|
q.push_back(x);
|
|
}
|
|
}
|
|
}
|
|
return 0;
|
|
}
|