首页 > 代码库 > UVA Ordering Tasks (经典拓扑排序)

UVA Ordering Tasks (经典拓扑排序)

技术分享

技术分享

   题意:n个任务,m组数据,每组数据输入x,y代表如果想要完成y任务需要先完成x任务,最后输出任务的完成顺序。


经典的拓扑排序。


代码:

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>

using namespace std;

int map[105][105];
int num[105];
int n,m;
int a[101];

void tp()
{
    queue<int>q;
    for(int i=1;i<=n;i++)
    {
        if(num[i] == 0)
        {
            q.push(i);
        }
    }
    int t;
    int e = 0;
    while(!q.empty())
    {
        t = q.front();
        a[e++] = t;
        q.pop();
        num[t]--;
        for(int j=1;j<=n;j++)
        {
            if(map[t][j] == 1)
            {
                num[j]--;
                if(num[j] == 0)
                {
                    q.push(j);
                }
            }
        }
    }
    for(int i=0;i<e;i++)
    {
        if(i<e-1)
        {
            printf("%d ",a[i]);
        }
        else
        {
            printf("%d\n",a[i]);
        }
    }
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n == 0 && m == 0)
        {
            break;
        }
        for(int i=1; i<=n; i++)
        {
            num[i] = 0;
            for(int j=1; j<=n; j++)
            {
                map[i][j] = 0;
            }
        }
        int x,y;
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&x,&y);
            if(map[x][y] == 0)
            {
                map[x][y] = 1;
                num[y]++;
            }

        }
        tp();
    }
    return 0;
}


UVA Ordering Tasks (经典拓扑排序)