题解 P1347 【排序】

· · 题解

这一道较为简单的拓扑排序题WA了3次才AC，我的思路跟大多数题解不同，发题解记录一下QwQ

我们将每个字母转化为一个点，只需要考虑整个图拓扑排序的情况。

这道题需要判断矛盾、得不到解的情况。

首先，如果这道题目改为：给出X条限制，判断这X条限制"是否矛盾"、"得到结果"与"条件不足"。

bfs版的拓扑排序是：首先将du[i]（入度）==0的点加入队列，然后每次取队列首，将所有队列首连向的点的入度--，分别判断每个连向的点，若入度为0，则再加入队列，直到队列为空为止。参考下面的伪代码：


for i in range[1,n] :
    i入队

while 队列不为空 :
    取队首u
    for u发出的边p :
        du[p->v]--; 
        //p所指向的点的入度--，也相当于把u发出的边都删去
        if du[p->v]==0 :
            p->v入队

首先，这样拓扑排序的结果是什么？

由于符合条件的点就入队，所以最终队列里的点的顺序就是拓扑排序中的队列所存的结果。

接下来考虑如何判断是否矛盾。

当没有入度为零的点的时候，显然条件有矛盾。 同时，当出现矛盾时，有些点的入度永远不会减到零，这就意味着这些点永远入不了队。

因此，当没有点入度为零，或当最终入队的点的个数<n的时候，条件有矛盾。

最后，我们考虑怎样判断条件不足。

如果最开始入度为零的点有不止一个，那么条件一定不足，因为这两个点的顺序无法确定。 同时，如果每次取队首时，有不止一个点入队了，那么条件一定不足，因为这两个点都只有队首连向的边。所以这两个点无法确定顺序。

另外就是，如果同时满足条件矛盾与条件不足，这时应该判定为条件矛盾。大家可以思考一下为什么（我就是因为这个WA的QwQ）

因此，当有不止一个点入度为零，或当取同一个队首u时有不止一个v的入度变成了零，则条件不足。

这道题数据范围比较小，所以只需要遍历每个1<=i<=m，用1~i条边建边，然后跑拓扑排序即可。如果条件矛盾或者条件充足直接输出即可，如果条件不足则继续加一条边重跑toposort。

附代码


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

const int maxn=30,maxm=905;

struct Node
{
    int v;
    Node *next;
}*h[maxn],pool[maxm];
int tot;
int du[maxn];
int q[maxn],head,tail;
int n,m;

void addEdge(int u, int v)
{
    Node *p=&pool[++tot];
    p->v=v; p->next=h[u]; h[u]=p;
}

int toposort() //返回值为1代表成立，返回值为0代表条件不足，返回值为-1代表条件矛盾
{
    int temp=0;
    int f=0;
    for(int i=1;i<=n;i++)
    {
        if(du[i]==0)
        {
            q[tail++]=i;
            temp++;
        } 
    }
    if(temp>1)
        f=1;
    while(head<tail)
    {
        temp=0;
        int u=q[head++];
        for(Node *p=h[u];p;p=p->next)
        {
            du[p->v]--;
            if(du[p->v]==0)
            {
                q[tail++]=p->v;
                temp++;
            }
        }
        if(temp>1)
            f=1;
    }
    if(tail!=n)
        return -1;
    else
        if(f==1)
            return 0;
    else return 1;
}   

struct Edge
{
    int u,v;
}a[maxm];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        char aa,bb,cc;
        cin>>aa>>bb>>cc;
        a[i].u=aa-'A'+1; a[i].v=cc-'A'+1;
    }
    for(int i=1;i<=m;i++)
    {
        addEdge(a[i].u,a[i].v);
        head = tail = 0;
        memset(du,0,sizeof(du));
        for(int j=1;j<=i;j++) du[a[j].v]++;
        int flag=toposort();
        if(flag==1)
        {
            cout<<"Sorted sequence determined after "<<i<<" relations: ";
            for(int j=0;j<=n-1;j++)
            {
                cout<<(char)(q[j]+'A'-1);
            }
            cout<<'.'<<endl;
            return 0;
        }
        else if(flag==0) continue;
        else
        {
            cout<<"Inconsistency found after ";
            cout<<i<<" relations."<<endl;
            return 0;
        }
    }
    cout<<"Sorted sequence cannot be determined."<<endl;
    return 0;
}