链式前向星dfs和bfs

 1 #pragma GCC optimize(2)
 2 #pragma GCC optimize(3)
 3 #include<bits/stdc++.h>
 4 using namespace std;
 5 const int N = 1e5+5;
 6 int head[N],cnt = 0;
 7 int vis[N];
 8 struct Edge{
 9     int to,next;
10 }e[N];
11 void addEdge(int u,int v){
12     cnt++;
13     e[cnt].to = v;
14     e[cnt].next = head[u];
15     head[u] = cnt;
16 }
17 void dfs(int u){
18     vis[u] = 1;
19     cout << u << " ";
20     for(int i=head[u];i;i=e[i].next){
21         if(!vis[e[i].to]){
22             dfs(e[i].to);
23         }
24     }
25 }
26 void bfs(int u){
27     vector<int> v;
28     queue<int> q;
29     q.push(u);
30     v.push_back(u); 
31     vis[u] = 1;
32     while(!q.empty()){
33         int t = q.front();q.pop();
34         for(int i=head[t];i;i=e[i].next){
35             if(!vis[e[i].to]){
36                 v.push_back(e[i].to);
37                 vis[e[i].to] = 1;
38                 q.push(e[i].to);
39             }
40         }
41     }
42     for(int i=0; i<v.size();i++){
43         cout << v[i] << " ";
44     } 
45 }
46 int main(){
47     ios::sync_with_stdio(0);
48     cin.tie(0);
49     cout.tie(0);
50     int n,m;
51     cin >> n >> m;
52     for(int i=1; i<=m; i++){
53         int u,v,w;
54         cin >> u >> v;
55         addEdge(u,v);
56     }
57     dfs(1);
58     cout << endl;
59     memset(vis,0,sizeof(vis));
60     bfs(1);
61     return 0;
62 }