Ordering Tasks 拓扑排序 UVA 10305

朴灿烈づ我的快乐病毒、 2024-02-17 18:54 13阅读 0赞

解题思路：c\[\]数组三种状态，-1（正在访问），0（未访问），1（已经访问）

为什么访问完一个结点之后要把它放在拓扑序列的首部：因为对于（u,v）两个元素，v始终比u先进入序列（当然是由于dfs的缘故啦）

1.  \#include<cstdio>
2.  \#include<cstring>
3.  const int maxn=100+5;
4.  int c\[maxn\];
5.  int topo\[maxn\];
6.  int G\[maxn\]\[maxn\];
7.  int t;
8.  int n,m;
9.  bool dfs(int u)\{ 
10.  c\[u\]=-1;
11.  for(int v=0;v<n;v++)if(G\[u\]\[v\])\{ 
12.  if(c\[v\]==-1)return false; //只要存在环，则无法完成排序
13.  if(!c\[v\] && !dfs(v)) return false;\} //如果第二个元素v未被访问 访问v为第一个元素存在环 返回假
14.   
    
15.  c\[u\]=1; //访问过的标记
16.  topo\[--t\]=u;
17.  return true;
18. \}
19.   
    
20. bool toposort()\{ 
21.  for(int u=0;u<n;u++)if(!c\[u\])\{ 
22.  if(!dfs(u))return false;
23.  \}
24.  return true;
25. \}
26. int main()\{ 
27.  while(scanf("%d%d",&n,&m)==2)\{ 
28.  if(n==0 && m==0)break;
29.  t=n;
30.  for(int i=0;i<m;i++)\{ 
31.  int a,b;
32.  scanf("%d%d",&a,&b);
33.  G\[a-1\]\[b-1\]=1;
34.  \}
35.  memset(c,0,sizeof(c));
36.  if(toposort())\{ 
37.  printf("%d",topo\[0\]+1);
38.  for(int i=1;i<n;i++)
39.  printf(" %d",topo\[i\]+1);
40.  \}
41.  printf("\\n");
42.  memset(G,0,sizeof(G)); //忘记清空G数组导致错了几次
43.  \}
44.  return 0;
45. \}

发表评论取消回复

表情：

评论列表（有 0 条评论，13人围观）

还没有评论，来说两句吧...

相关阅读

相关 Ordering Tasks 拓扑排序 UVA 10305

解题思路：c\[\]数组三种状态，-1（正在访问），0（未访问），1（已经访问）为什么访问完一个结点之后要把它放在拓扑序列的首部：因为对于（u,v）两个元素，v始终比u先进

朴灿烈づ我的快乐病毒、/ 2024年02月17日 18:54/ 0 赞/ 14 阅读

相关拓扑次序(Topological Order)

对一个[有向无环图][Link 1](Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边

深碍√TFBOYSˉ_/ 2022年09月08日 15:50/ 0 赞/ 105 阅读

相关 pku 1270 Following Orders DFS+拓扑排序

题意很清晰. 可以利用dfs遍历每一组值,然后加上剪枝条件. 由于剪枝可以利用当前节点和已遍历节点的顺序关系,可以使用拓扑排序. 注意: 输入的第一行不一定是有序的,我在

电玩女神/ 2022年08月09日 14:52/ 0 赞/ 26 阅读

相关 Ordering Tasks-简单的拓扑排序

[原题在这里^\_^][Link 1] 题意：通过输入m条两任务间的优先顺序，输出一个可能的任务顺序；思路；拓扑排序，就是建立一个图，每次选择入度为零的顶点，将与之

女爷i/ 2022年06月11日 00:13/ 0 赞/ 123 阅读

相关拓扑排序

什么是拓扑排序? 在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序

冷不防/ 2022年06月09日 05:57/ 0 赞/ 232 阅读

相关拓扑排序

拓扑排序一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就

小鱼儿/ 2022年04月10日 08:23/ 0 赞/ 257 阅读

相关 (PAT 1146) Topological Order (拓扑排序)

This is a problem given in the Graduate Entrance Exam in 2018: Which of the following is

╰+哭是因爲堅強的太久メ/ 2022年03月19日 03:46/ 0 赞/ 151 阅读

相关 Ordering Tasks UVA 10305(拓扑排序)

John has n tasks to do. Unfortunately, the tasks are not independent and the execution o

客官°小女子只卖身不卖艺/ 2022年02月26日 02:18/ 0 赞/ 107 阅读

相关拓扑排序

拓扑排序：拓扑排序是根据离散数学中有关偏序与全序定义的。 ![0_1314168765l7fq.gif][] 若一个集合 X 上的关系 R 是自反的反

淩亂°似流年/ 2021年12月23日 02:43/ 0 赞/ 356 阅读

相关拓扑排序

一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程

野性酷女/ 2021年09月19日 05:04/ 0 赞/ 464 阅读