网站流量检测,wordpress调二级分类目录,做网站挣钱么,网站支付的功能如何做一.定义 拓扑排序是一种对有向无环图#xff08;DAG#xff09;进行排序的算法#xff0c;使得图中的每个顶点在排序中都位于其依赖的顶点之后。它通常用于表示一些任务之间的依赖关系#xff0c;例如在一个项目中#xff0c;某些任务必须在其他任务之前完成。
拓扑排序的…一.定义 拓扑排序是一种对有向无环图DAG进行排序的算法使得图中的每个顶点在排序中都位于其依赖的顶点之后。它通常用于表示一些任务之间的依赖关系例如在一个项目中某些任务必须在其他任务之前完成。
拓扑排序的步骤如下 找到入度为0的顶点入度是指指向某个顶点的边的数量。首先找到图中入度为0的顶点它们是没有依赖关系的顶点可以作为排序的起点。 将入度为0的顶点移出图选择一个入度为0的顶点将其从图中移除并将与之相邻的顶点的入度减1。 重复步骤1和步骤2重复上述步骤直到所有顶点都被移除。如果图是有向无环图那么拓扑排序会成功完成。
拓扑排序并不是对所有图都适用只有在有向无环图中才有意义因为循环依赖会导致拓扑排序无法进行。 二.例题
B3644 【模板】拓扑排序 / 家谱树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 三.思路
找出入度为0的点即为最小辈分的输出即可然后取消它的所有连边。
eg 可知2无入度说明2的辈分最小输出并删除它的连边print(2) 这时4无入度,print(2,4) 一直重复print(2,4,5,3,1) 四.参考代码
#includebits/stdc.h
using namespace std;
vectorintto[101];
int in[101];
queueintq;
int main(){int n;scanf(%d,n);for(int i1;in;i){int x;while(scanf(%d,x) x!0){to[i].push_back(x);in[x];}}for(int i1;in;i){if(!in[i]) q.push(i);}while(!q.empty()){int xq.front();q.pop();coutx ;for(int i0;ito[x].size();i){int yto[x][i];in[y]--;if(!in[y]) q.push(y);}}return 0;
}五.拓扑dp
P1807 最长路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 六.思路
不就是最长路吗Dijkstra直接秒杀。
但还有什么更快的算法吗
注意这是有向无环图DAG是不是拓扑排序更快呢拓扑排序就可以找到图的所有直径然后DP即可。最后输出dp[n];
状态转移方程为dp[v]max(dp[v],dp[u]w);
若dp[n]0那就说明没有边可以到达n点 七.参考代码
#includebits/stdc.h
#define maxn 1505
using namespace std;
int n,m;
vectorint to[maxn],wt[maxn];
int in[maxn],dp[maxn];
queueint q;
int main(){scanf(%d%d,n,m);for(int i1;im;i){int u,v,w;scanf(%d%d%d,u,v,w);to[u].push_back(v);wt[u].push_back(w);in[v]; }for(int i1;in;i){dp[i]-1e9;if(in[i]0) q.push(i) ;}dp[1]0;while(!q.empty()){int xq.front(); q.pop();for(int i0;ito[x].size();i){int yto[x][i],wwt[x][i];dp[y]max(dp[y],dp[x]w);in[y]--;if(!in[y]) q.push(y);}}if(dp[n]0) cout-1;else coutdp[n];return 0;
}
