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

UVA 10305 Ordering Tasks (拓扑排序)

题意:给你n个点、m个关系,每个关系两个点u、v,表示u小于v,叫你输出任意一个序列保证满足所有给定的关系

   例如:n=3 m=2

      1 2

      3 1

      3 2

      3 1 2

 

题解:拓扑排序排的是一个有向无环图(DAG),首先没有回路,否则会失败,其次如果存在G(u,v),则在该序列中u在v前面

   实现方法就是遍历每个点,当此点没被标记过就进入递归

   然后将此点看做树的根节点(DAG其实可以看做森林),遍历它可以到的所有点,最后从后向前将点加入排序的序列并标记

 

#include<cstdio>
#include<cstring>
const int Max=105;
int graph[Max][Max];
int topo[Max];
int vis[Max],t;
bool topoDfs(int u,int n)//进入u极其u的后面所有点
{
    vis[u]=-1;//表示正在访问
    for(int v=1; v<=n; ++v)
    {
        if(graph[u][v])
        {
            if(vis[v]==-1)//有环
                return false;
            if(!vis[v]&&!topoDfs(v,n))//没被访问过才进入
                return false;
        }
    }
    vis[u]=1;//表示已经访问过
    topo[--t]=u;//注意加入后面
    return true;
}
void topoSort(int n)
{
    memset(vis,0,sizeof(vis));
    t=n;
    for(int i=1; i<=n; ++i)
    {
        if(!vis[i])//表示没有访问过它极其它后面的节点
        {
            if(!topoDfs(i,n))//此点极其它后面的点都进dfs
            {
                return ;//图是有环的
            }
        }
    }
}
int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m)&&(n+m))
    {
        for(int i=0; i<=n; ++i)
        {
            for(int j=0; j<=n; ++j)
            {
                graph[i][j]=0;
            }
        }
        int u,v;
        for(int i=0; i<m; ++i)
        {
            scanf("%d %d",&u,&v);
            graph[u][v]=1;
        }
        topoSort(n);
        for(int i=0; i<n; ++i)
        {
            printf("%d%c",topo[i],i==n-1?\n: );
        }
    }
}

 

UVA 10305 Ordering Tasks (拓扑排序)