首页 > 代码库 > UVA10305 Ordering Tasks【DFS】【拓扑排序】

UVA10305 Ordering Tasks【DFS】【拓扑排序】

2024-08-07 16:52:42   218人阅读

Ordering Tasks
Input: standard input
Output: standard output
Time Limit: 1 second
Memory Limit: 32 MB
 

John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task is only possible if other tasks have already been executed.


Input

The input will consist of several instances of the problem. Each instance begins with a line containing two integers, 1 <= n <= 100 and m. n is the number of tasks (numbered from 1 to n) and m is the number of direct precedence relations between tasks. After this, there will be m lines with two integers i and j, representing the fact that task i must be executed before task j. An instance with n = m = 0 will finish the input.


Output

For each instance, print a line with n integers representing the tasks in a possible order of execution.

Sample Input

5 4
1 2
2 3
1 3
1 5

0 0


Sample Output

1 4 2 5 3

(The Joint Effort Contest, Problem setter: Rodrigo Malta Schmidt)


题目大意：有n个变量，和m个二元组关系。关系(x,y)表示x<y。现在讲所有变量

从小到大来排序，进行输出。

例如：有4个变量a、b、c、d，若a<b，c<b，d<c，则排序后的可能为a<d<c<b，

也有其他可能d<a<c<d。只要输入其中一个就可。

思路：把n个变量看成是n个点，“x<y”看做是一条边，则得到一个有向图。对图的

节点进行排序，使得每一条有向边(x,y)对应的x都在y前边。即所谓的拓扑排序。

DFS进行拓扑排序,如果存在有向环，则不存在拓扑排序，否则就将访问完的结点

假如到当前拓扑序列的前边。具体过程参考代码。

参考：算法竞赛入门经典(第二版)P168~169


#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

int vis[1100];
int topo[1100],G[1100][1100],t,n,m;
bool dfs(int u)
{
    vis[u] = -1;//开始访问结点
    for(int v = 0; v < n; v++)
    {
        if(G[u][v])//存在边
        {
            if(vis[v]<0)//表示结点v正在访问中，(即调用dfs(u)还在栈中，尚未返回)
                return false;
            else if(!vis[v])//没有访问过该结点
                dfs(v);//访问该结点
        }
    }

    vis[u] = 1;//结点访问结点
    topo[--t] = u;//存储当前结点到拓扑序的首部
    return true;
}

bool toposort()
{
    t = n;
    memset(vis,0,sizeof(vis));
    for(int u = 0; u < n; u++)
    {
        if(!vis[u])
            if(!dfs(u))
                return false;
    }
    return true;
}

int main()
{
    while(~scanf("%d%d",&n, &m) && (n||m))
    {
        memset(G,0,sizeof(G));
        while(m--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G[--u][--v] = 1;
        }
        if(toposort())
        {
            for(int i = 0; i < n; i++)
            {
                if(i!=n-1)
                    printf("%d ",topo[i]+1);
                else
                    printf("%d\n",topo[i]+1);
            }
        }
        else
            printf("No\n");
    }

    return 0;
}


UVA10305 Ordering Tasks【DFS】【拓扑排序】


联系
我们