拓扑排序-POJ1964

拓扑排序

1.什么是拓扑排序？

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

也就是说排序后的一个顶点不存在指向他前面顶点的边。

2.拓扑排序的应用？

拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。

3.怎样进行拓扑排序？

对于一个给定的图，先找到入度为0的点，那么这个点就是排序后的第一个顶点，然后将他指向顶点的入度减1，再寻找下一个入度为0的顶点直至找到所有顶点，但是拓扑排序不能应用在有环图中，因为有环图不存在入度为0的顶点。

int topsort(int x)
{
    priority_queue<int ,vector<int> ,greater<int > >q;
    int flag=0,k;
    int zeroflag=0;
    int num=0;
    memcpy(temp,in,sizeof(in));
    for(int i=0;i<n;i++)
    {
        if(in[i]==0) q.push(i);
    }
    while(!q.empty())
    {
        if(q.size()>1) zeroflag=1;
        k=q.top();
        q.pop();
        num++;
        ans[num]=k+'A';
     for(int i =  0 ; i < x; i++ )
            if(map[k][i]==1 && --temp[i] == 0)
                q.push(i);     
    }
    //cout<<num<<" "<<x<<endl;
    if(num!= x) return 1;
    if(zeroflag==1) return 0;
    return -1;
}

========================================分隔符=============================================================

POJ 1964 SORTING IT ALL

题目链接：https://vjudge.net/problem/POJ-1094

题目大意：对于n个大写字母，给你他们的关系，问经过多少个关系的判断后，可以判断出他们之见是否能够进行排序或者他们之间的关系有冲突

这道题对于每次输入的关系我们都要进行以此判断，除了样列外，比如给你以下三种关系，

A<B,B<C,C<A这时候很明显A,B,C之间形成了一个环，但是在输入了前两个关系后，我们就可以确定ABC三者之间的关系，所以答案应该输出的是可以排序而不是

存在环。

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
#define maxn 50
int n,m;
int in[maxn],temp[maxn];
bool map[maxn][maxn];
char ans[maxn];
int topsort(int x)
{
    priority_queue<int ,vector<int> ,greater<int > >q;
    int flag=0,k;
    int zeroflag=0;
    int num=0;
    memcpy(temp,in,sizeof(in));
    for(int i=0;i<n;i++)
    {
        if(in[i]==0) q.push(i);
    }
    while(!q.empty())
    {
        if(q.size()>1) zeroflag=1;
        k=q.top();
        q.pop();
        num++;
        ans[num]=k+'A';
     for(int i =  0 ; i < x; i++ )
            if(map[k][i]==1 && --temp[i] == 0)
                q.push(i);     
    }
    //cout<<num<<" "<<x<<endl;
    if(num!= x) return 1;
    if(zeroflag==1) return 0;
    return -1;
}
int main()
{
    int step,circleflag,orderflag;
    char s[5];
    while(cin>>n>>m)
    {
     circleflag=0;orderflag=0;
        if(n==0&&m==0) return 0;
        memset(map,0,sizeof(map));
        memset(in,0,sizeof(in));
        for(int i=1;i<=m;i++)
        {
            scanf("%s",s);
            if(circleflag==0&&orderflag==0)
            {
                if(map[s[2]-'A'][s[0]-'A']==1)
                {
                    circleflag=1;
                    printf("Inconsistency found after %d relations.
", i);
                    continue;
                }
                if(map[s[0]-'A'][s[2]-'A']==0)
                {
                    map[s[0]-'A'][s[2]-'A']=1;
                    in[s[2]-'A']++;
                }
                int k=topsort(n);
                if(k==1)
                {
                    circleflag=1;
                    printf("Inconsistency found after %d relations.
", i);
                }
                else if(k==-1)
                {
                    orderflag=1;
                    step=i;
                }
            }
        }
        if(circleflag==0&&orderflag==0)
     printf("Sorted sequence cannot be determined.
");
        else if(orderflag==1)
        {
            printf("Sorted sequence determined after %d relations: ", step);
            for(int i=1;i<=n;i++)
            {
                printf("%c",ans[i]);
                
            }
            printf(".
");
        }        
    }
    return 0;
}

AC CODE

对于题意还可以看这篇博客：https://blog.csdn.net/lyy289065406/article/details/6645999

^-^