中考一段时间没有勤加练习,如今已经沦落到搜索跑图还会3WA 2TLE的地步了......
代码奉上:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define N 100005
#define E 1000005
#define inf 1e10
queue<int>q;//bfs存入点
int num,head[E];
int n,m;
bool vis[N];
struct Edge{
int next;
int sta;
int to;
//int val;
}edge[E];
bool cmp(Edge x,Edge y)//由于先看编号较小的,因此需要按照终点排序
{
if(x.to==y.to)return x.sta>y.sta;//若终点相同,则按起点排序
return x.to>y.to;//前向星是逆序查找,因而调整使终点较小的边较后
}
void AddEdge(int x,int y)
{
edge[++num].next=head[x];
edge[num].sta=x;
edge[num].to=y;
head[x]=num;
}//前向星存边
void dfs(int p)
{
if(vis[p])return;
cout<<p<<' ';//当前搜索到了p点
vis[p]=true;
for(register int i=head[p];i!=-1;i=edge[i].next)
dfs(edge[i].to);//深入下个节点
}
void bfs(int p)
{
q.push(p);
while(!q.empty())
{
int z=q.front();
q.pop();
cout<<z<<' ';
vis[z]=true;//已访问
for(register int i=head[z];i!=-1;i=edge[i].next)//枚举边
if(!vis[edge[i].to])q.push(edge[i].to);//bfs入队
}
}
int main()
{
ios::sync_with_stdio(false);
memset(head,-1,sizeof(head));//dfs枚举边
cin>>n>>m;
for(register int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
AddEdge(x,y);
}
sort(edge+1,edge+m+1,cmp);//排序
memset(vis,false,sizeof(vis)); //是否访问过
dfs(1);
cout<<'\n';
memset(vis,false,sizeof(vis));
bfs(1);
return 0;
}
恳请各位大佬指明错误之处~