拓扑排序
拓扑序列大概就是指把每个入度为0的节点依次删除,删除的顺序所得的序列,并且这样的序列是不唯一的。
因为印象中拓扑排序是可以深搜写的所以就用了深搜,不过深搜和广搜都差不多几乎是一模一样的。
代码
#include<cstdio>
using namespace std;
const int sz=1e5+1;
int d[sz],v[sz],h[sz],nt[sz],n,m,ct,sss,s[sz];
void add(int x,int y){v[++ct]=y,nt[ct]=h[x],++d[y],h[x]=ct;}
void topsort(int x)
{
int i,y;
for(i=h[x];y=v[i],i;i=nt[i])
if(--d[y]==0)
s[++sss]=y,f[y]=1,tpx(y);
}
int main()
{
int i,x,y;
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i)scanf("%d%d",&x,&y),add(x,y);
for(i=1;i<=n;++i)if(!d[i]){x=i;break;}
topsort(x);
for(i=1;i<=n;++i)if(d[i]){printf("-1");return 0;}
printf("1");
for(i=1;i<=sss;++i)printf(" %d",s[i]);
return 0;
}
对了要看清楚题目意思,我最开始是在深搜里输出的。
但因为有可能会有环所以要输出无解的情况,这样的话得用一个数组来存储。