zzoce 🧊
s
l
O(E+V)
12345678910111213141516171819202122232425262728293031323334
void toposort() {//拓扑排序 for (int u=1;u<=n;u++){//统计入度 for (int i=head[u];~i;i=edge[i].next){ to_head[edge[i].to]++; } } queue<int> s; for (int i=1;i<=n;i++){ //入度为零进队 if (to_head[i]==0){ s.push(i); } } while (!s.empty()){ int u=s.front(); s.pop(); //出队顺序就是拓扑顺序。 l.push_back(u); for (int v=head[u];~v;v=edge[v].next){ if (--to_head[edge[v].to]==0){ s.push(edge[v].to); } } } if (l.size()==n){ for (int v:l){ cout<<v<<endl; } } }
将 Kahn 算法中的队列替换成最大堆/最小堆实现的[[STL#优先队列|优先队列]]即可,此时总的时间复杂度为O(E+VlogV)。
O(E+VlogV)