https://www.luogu.com.cn/problem/P5318
存储一：邻接表
1 #include<cstdio> 2 #include<vector> 3 #include<queue> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 int n, m, x, y; 8 const int maxn=100005; 9 vector<int>a[maxn];//可变的二维数组：邻接表 10 bool vis[maxn];//标识是否被访问 11 void dfs(int v){ 12 printf("%d ",v); 13 vis[v]=1; 14 for(int i=0; i<a[v].size(); i++){ 15 int t=a[v][i]; 16 if(!vis[t]) 17 dfs(t); 18 } 19 } 20 void bfs(int v){ 21 queue<int> que; 22 que.push(v); 23 vis[que.front()]=1; 24 while(!que.empty()){ 25 int t=que.front(); 26 for(int i=0; i<a[t].size(); i++){ 27 int tt=a[t][i]; 28 if(!vis[tt]){ 29 que.push(tt); 30 vis[tt]=1; 31 } 32 } 33 printf("%d ",que.front()); 34 que.pop(); 35 } 36 } 37 int main() 38 { 39 scanf("%d%d",&n, &m); 40 for(int i=1; i<=m; i++){ 41 scanf("%d%d", &x, &y); 42 a[x].push_back(y); 43 } 44 for(int i=1; i<=n; i++)//对每一行进行排序 45 sort(a[i].begin(), a[i].end());//对vector进行排序 46 47 //测试代码 48 // for(int i=1; i<=n; i++){ 49 // printf("%d:",i); 50 // for(int j=0; j<a[i].size(); j++) 51 // printf("%d ", a[i][j]); 52 // printf(" "); 53 // } 54 //图的遍历 55 memset(vis, 0, sizeof(vis)); 56 dfs(1); 57 printf(" "); 58 memset(vis, 0, sizeof(vis)); 59 bfs(1); 60 61 return 0; 62 }