拓扑排序 喜欢ヅ旅行 2021-06-22 15:37 477阅读 0赞 ## 作用:判断是否存在环 ## 1.数组模拟队列 #include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; const int maxn=1e5+10; int h[maxn],e[maxn],ne[maxn],idx,d[maxn];//d[]表示该点的入度 int q[maxn],hh,tt=-1; int n,m; void add(int a,int b){ //邻接表 e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } bool top_sort(){ for(int i=1;i<=n;i++){ if(d[i]==0){ q[++tt]=i;// 将所有入度为0的点加入队列 } } while(tt>=hh){ int t=q[hh++];//取出队头删掉队头 for(int i=h[t];i!=-1;i=ne[i]){ int j=e[i]; d[j]--; if(d[j]==0){ q[++tt]=j;//如果 j 入度为0,加入队列当中 } } } if(tt==n-1){ //如果队列已经存放满了n个元素说明没有环 return true; } return false; } int main(){ memset(h,-1,sizeof(h));//初始化链表的表头 cin>>n>>m; while(m--){ int a,b; cin>>a>>b; add(a,b); d[b]++;//b的入度加1 } if(top_sort()){ for(int i=0;i<=tt;i++){ //如果是真说明不存在环直接把队列的元素输出 cout<<q[i]<<" "; } } else{ cout<<-1<<endl;//有环不存在拓扑序列 } return 0; } 2.stl容器 #include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <queue> using namespace std; const int maxn=1e5+10; int n,m; vector<int> ans; int h[maxn],e[maxn],ne[maxn],idx,d[maxn];//d[]表示该点的入度 void add(int a,int b){ e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } bool top_sort(){ queue<int> q; for(int i=1;i<=n;i++){ if(d[i]==0){ q.push(i);// 将所有入度为0的点加入队列 } } while(!q.empty()){ //当队列不空时 int t=q.front(); ans.push_back(t);//存起来备份方便输出 q.pop(); for(int i=h[t];i!=-1;i=ne[i]){ int j=e[i]; d[j]--;//减去已经前一个点到当前该点的入度 if(d[j]==0){ q.push(j);//如果 j 入度为0,加入队列当中 } } } if(ans.size()==n){ return true;//如果队列已经存放满了n个元素说明没有环 } return false; } int main(){ memset(h,-1,sizeof(h));//初始化链表的表头 cin>>n>>m; while(m--){ int a,b; cin>>a>>b; add(a,b); d[b]++;//b的入度加1 } if(top_sort()){ for(int i=0;i<ans.size();i++){ cout<<ans[i]<<" "; } } else{ cout<<-1<<endl; } }
相关 拓扑排序 在这里我们引入AOV(Activity-On-Vertex)网,图的顶点代表活动,其有向边<Vi,Vj>代表完成Vj之前Vi必须先完成。 对于一个工程,我们首先将这 野性酷女/ 2022年06月10日 13:28/ 0 赞/ 198 阅读
相关 拓扑排序 C++版本实现 /以邻接矩阵Edge[A][B]=N存放图信息:A指向B,权值为N/ /假设不相连的边的Edge==INT_MAX/ void 淡淡的烟草味﹌/ 2022年06月09日 05:58/ 0 赞/ 329 阅读
相关 拓扑排序 什么是拓扑排序? 在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序 冷不防/ 2022年06月09日 05:57/ 0 赞/ 186 阅读
相关 拓扑排序 拓 扑 排 序 一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就 小鱼儿/ 2022年04月10日 08:23/ 0 赞/ 213 阅读
相关 拓扑排序 (1)有向无环图 无环的有向图,简称 DAG (Directed Acycline Graph) 图。 有向无环图在工程计划和管理方面的应用:除最简单的情况之外,几 古城微笑少年丶/ 2022年03月18日 12:35/ 0 赞/ 247 阅读
相关 拓扑排序 拓扑排序: 拓扑排序是根据离散数学中有关偏序与全序定义的。 ![0_1314168765l7fq.gif][] 若一个集合 X 上的关系 R 是自反的 反 淩亂°似流年/ 2021年12月23日 02:43/ 0 赞/ 296 阅读
相关 拓扑排序 拓扑排序 题目做的烦,题解写着玩 [POJ 2762 Going from u to v or from v to u?][POJ 2762 Going from 谁借莪1个温暖的怀抱¢/ 2021年12月20日 16:11/ 0 赞/ 243 阅读
相关 拓扑排序 一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就是说,一个子工程 野性酷女/ 2021年09月19日 05:04/ 0 赞/ 405 阅读
相关 拓扑排序 作用:判断是否存在环 1.数组模拟队列 include <iostream> include <vector> include <cst 喜欢ヅ旅行/ 2021年06月22日 15:37/ 0 赞/ 478 阅读
还没有评论,来说两句吧...