讲解

 代码  P5318【深基18.例3】查找文献

#include <bits/stdc++.h>
using namespace std;

const int N=100010;
vector<int> a[N];
int n, m, x, y, vis[N];
queue<int> q;
void dfs(int s)
{
	if (vis[s]==1) return;
	vis[s]=1;
	printf("%d ", s);
	for (int i=0; i<a[s].size(); i++)
		dfs(a[s][i]);
}
void bfs(int s)
{
	printf("%d ", s);
	q.push(s);
	vis[s]=1;
	while (!q.empty())
	{
		int t=q.front();
		q.pop();
		for (int i=0; i<a[t].size(); i++)
			if (vis[a[t][i]]!=1) 
			{
				vis[a[t][i]]=1;
				q.push(a[t][i]);
				printf("%d ", a[t][i]);
			}
	}
}
int main()
{
	scanf("%d%d", &n, &m);	
	//建图 
	for (int i=1; i<=m; i++)
	{
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		//a[y].push_back(x);   有向图无需存 
	}
	for (int i=1; i<=n; i++)
		sort(a[i].begin(), a[i].end());
	
	//遍历
	memset(vis, 0, sizeof(vis));
	dfs(1);
	printf("\n");
	memset(vis, 0, sizeof(vis));
	bfs(1);
	return 0;
}