算法描述

先讲所有的边按照起点和终点的编号从小到大排序，然后将$i$的所有的参考文献储存到动态数组$g[i]$之中,接下来对数组进行dfs和bfs。

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define u first
#define v second
const int N=1e5+10,M=1e6+10;
PII edge[M];
int ans[M],st[M];
vector<int> g[M];
void bfs()
{
	queue<int> q;
	q.push(1);
	st[1]=1;
	cout<<1<<" ";
	while(q.size())
	{
		int t=q.front(); //获取队头元素 
		q.pop();
		for(int i=0;i<g[t].size();i++) //遍历当前这层 
		{
			int j=g[t][i];
			if(!st[j])
			{
			q.push(j);
			st[j]=1;
			cout<<j<<" ";
		}
		}
	}
}
void dfs(int x)
{
	cout<<x<<" ";
	st[x]=1;
	for(int i=0;i<g[x].size();i++) //遍历所有孩子节点 
	{
		int j=g[x][i];
		if(st[j]) continue; //已经遍历过 
		dfs(j); //继续遍历孩子节点 
	} 
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		cin>>edge[i].u>>edge[i].v;
	}
	sort(edge,edge+m); //按照文献的编号从小到大排序 
	for(int i=0;i<m;i++) //使用邻接表存树/图 
	{
		g[edge[i].u].push_back(edge[i].v);
	}
	dfs(1); //从根节点开始遍历 
	memset(st,0,sizeof st); //清空 
	cout<<endl;
	bfs();
	return 0;
}