题解 P1347 【排序】

这道题一开始什么思路都没有,最后还是看了标签;

然后经过大神的一句话;

判断是否会连成环;

这道题判断最好用floyd;

因为好写;

一旦出现环,自然是矛盾,输出,然后exit(0);

如果没有环,就深搜一边;

如果可以把所以有的点都遍历到;

就直接输出成立;

否则;

如果所有的都输入完了,还是不能判断;

就输出无法判断;

还有一点就是每输入一次就判断一次,即做一遍以上步骤;

最好dfs时用vector或者链式前向星加速,不然第九个点会TLE;

以及成立的时候输出的东西后有个句点;

#include<iostream>
#include<cstdio>
#include<algorithm>
#define II int
#define C char
#define R register
#define IL inline
#define I 30
using namespace std;

struct node {
    II to,up;
}aa[I];

II head[I*123];

II _tot;

void add(R II x,R II y)
{
    aa[++_tot].to=y;
    aa[_tot].up=head[x];
    head[x]=_tot;
}

II had[I], f[I][I], ans[I], in[I];

II n,m,now;

IL II can()
{
    for(R II i=1;i<=26;i++)
    {
        for(R II j=1;j<=26;j++)
        {
            for(R II k=1;k<=26;k++)
            {
                f[j][k]=max(f[j][k],f[j][i]&f[i][k]);
            }
        }
    }

    for(R II i=1;i<=26;i++) if(f[i][i]) return 0; 
    return 1;
}

IL II dfs(R II x,R II ka)
{
    ans[ka]=x;
    if(ka==n) return 1;
    for(R II i=head[x];i;i=aa[i].up)
    {
        II g=aa[i].to;
        if(!had[g]) {
            had[g]=1;
            if(dfs(g,ka+1)) return 1; 
            had[g]=0;
        }
    }
    return 0;
}

int main()
{
//    freopen("1.in","r",stdin);

    scanf("%d%d",&n,&m);
    for(R II i=1;i<=m;i++)
    {
        R C a,b,z;
        cin>>a>>z>>b;
        R II ka1=a-'A'+1;
        R II ka2=b-'A'+1;
        f[ka1][ka2]=1;
        add(ka1,ka2);
        in[ka2]++;

        if(!can()) {
            printf("Inconsistency found after %d relations.\n",i);
            exit(0);
        } else {
            for(R II j=1;j<=26;j++)
            {
                if(!in[j]) {
                    for(R II k=1;k<=26;k++) had[k]=0;
                    if(dfs(j,1)) {
                        printf("Sorted sequence determined after %d relations: ",i);
                        for(R II k=1;k<=n;k++) printf("%c",ans[k]-1+'A');
                        cout<<'.'<<endl;
                        exit(0); 
                    }
                }
            }
        }
    }

    printf("Sorted sequence cannot be determined.\n");
    exit(0);
}

发表于 2017-09-21 14:08:20 in 题解