MYF

UVa 10305 Ordering Tasks

Posted on | In | | Visitors

题目链接

UVa 10305

解题方法：拓扑排序(DFS)

题目分析

题目大意

给定n个任务，有m组优先顺序，如1 2，表示完成任务2之前必须完成任务1。问：完成这n个任务的任意一个符合条件的排列顺序。

解析

这题一开始以为是判断能否完成任务，后来发现是要求输出顺序，存在优先级的顺序问题，所以采用拓扑排序，根据紫书上的模版敲的，后来发现给的模版就是用于这道题的。

吐槽：本来代码就是对的，然而交了五六发全是WA，后来代码发给队友，人家给我加了几个括号Ac了……Ac了……Ac了……凌乱。

拓扑排序(DFS版)个人理解

总共n个点(0～n-1)，m组关系。

t：topo数组反向记录时的位置下标。

G数组：邻接矩阵 G[u][v]=1表示 u到v单向连通。

c数组：0表示未访问，1表示已找过，－1表示在DFS递归中。

topo数组：记录拓扑排序后的结果。

从第一个点开始找，对每一个点一直递归，递归的层数越深(即在图中越靠上)，越先进入topo数组尾部。
图示

各点的访问顺序：正向访问

————————>

1 2 3 4 5 6 7 8 … n

topo数组的填入顺序：反向填入

<————————

1 2 3 4 5 6 7 8 … n

toposort()函数返回该图是否出环
topo[]数组储存最终结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, n) for (int i = 1; i <= n; i++)
#define ForK(i, k, n) for (int i = k; i <= n; i++)
#define ForD(i, n) for (int i = n; i >= 0; i--)
#define Rep(i, n) for (int i = 0; i < n; i++)
#define RepD(i, n) for (int i = n; i >= 0; i--)
#define MemI(a) memset(a, 0, sizeof(a))
#define MemC(a) memset(a, '\0', sizeof(a))
#define vset(a,val) memset(a,val,sizeof(a))
#define pf          printf
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define PI acos(-1)
#define bug         pf("Hi----------\n")
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
int m;
/*****模版部分****/
const int maxn=1005;
int G[maxn][maxn];//邻接矩阵
int n;
int c[maxn];
int topo[maxn],t;
bool dfs(int u)
{
    c[u]=-1;//访问标志
    for (int v=0; v<n; v++){
        if (G[u][v])
        {
            if (c[v]<0) return false;
            else if (!c[v]&&!dfs(v)) return false;
        }
        
    }
    c[u]=1;
    topo[--t]=u;
    return true;
}
bool toposort()
{
    t=n;
    memset(c,0,sizeof(c));
    for (int u=0; u<n; u++)
        if (!c[u]&&!dfs(u)) return false;
    return true;
}
/*****模版部分****/
int main()
{
    
    while (scanf("%d %d",&n,&m)!=EOF)
    {
        if (n==0&&m==0)
            break;
        memset(G, 0, sizeof(G));
        for (int i=0; i<m; i++)
        {
            int u,v;
            scanf("%d %d",&u,&v);
            G[u-1][v-1]=1;
        }
        toposort();
        for (int i=0; i<n; i++)
        {
            if (i==0)
                printf("%d",topo[i]+1);
            else
                printf(" %d",topo[i]+1);
        }
        printf("\n");
    }
    return 0;
}