美妆网站建设规划,大朗做网站,品牌建设的基本原则,自己网站页面设计软件拓扑排序的流程#xff1a;
插入#xff08;a#xff0c;b#xff09;#xff0c;表示a-b的关系#xff0c;调用add(a,b),每次吧b的入度1#xff0c;d[b]; 然后调用topsort#xff0c;返回1表示存在拓扑序列#xff0c;返回0表示不存在拓扑序列。判断是否存在拓扑…拓扑排序的流程
插入ab表示a-b的关系调用add(a,b),每次吧b的入度1d[b]; 然后调用topsort返回1表示存在拓扑序列返回0表示不存在拓扑序列。判断是否存在拓扑排序的逻辑 先把所有入度为0的点入队这些都是可能的结果。 取出队头t然后出队 因为是拉链法表示的有向图因此访问t对应的所有出边je【i】 然后删除t-j的关系把j的入度-1d[j] --,如果-1之后发现j的入度为0那么j依然可能是新的拓扑序列的一员需要把j入队如果拓扑排序完了之后把所有的点都曾入队过那么存在拓扑序列。
#includeiostream
#includealgorithm
#includecstring
#define N 100086
using namespace std;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];
void add(int a,int b){e[idx]b,ne[idx]h[a],h[a]idx;
}
bool topsort(){int hh0,tt-1;for(int i1;in;i)if(!d[i])q[tt]i;while(hhtt){int tq[hh];for(int ih[t];i!-1;ine[i]){int je[i];if(--d[j]0){q[tt]j;}}}return ttn-1;
}
int main(){cinnm;memset(h,-1,sizeof h);for(int i0;im;i){int a,b;cinab;add(a,b);d[b];}if(!topsort())puts(-1);else{for(int i0;in;i)coutq[i] ;puts();}return 0;
}
