rt,链式前向星式存图

#include<bits/stdc++.h>
using namespace std;
int tot,Next[1000005],Head[100005],Son[100005],t[100005],q[100005],head,tail,n,m;
struct XX
{
	int u,v;
}a[1000005];
void add(int x,int y)
{
	tot++;
	Next[tot]=Head[x];
	Son[tot]=y;
	Head[x]=tot;
}
void dfs(int x)
{
	cout<<x<<' ';
	t[x]=1;
	for(int i=Head[x];i;i=Next[i])if(!t[Son[i]])dfs(Son[i]);
}
void bfs(int x)
{
	q[1]=t[1]=1;
	cout<<"1 ";
	head=1;
	tail=1;
	while(head<=tail)
	{
		x=q[head];
		for(int i=Head[x];i;i=Next[i])
			if(!t[Son[i]])
			{
				tail++;
				cout<<Son[i]<<' ';
				q[tail]=Son[i];
				t[Son[i]]=1;
			}
		head++;
	}
}
bool cmp(XX x,XX y){return x.u==y.u?x.v>y.v:x.u<y.u;}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>a[i].u>>a[i].v;
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++)add(a[i].u,a[i].v);
	dfs(1);
	cout<<'\n';
	memset(t,0,sizeof(t));
	bfs(1);
}