POJ 1270 Following Orders(拓扑排序:输出所有可能)

POJ 1270 Following Orders(拓扑排序:输出所有可能)

http://poj.org/problem?id=1270

题意:输入数据有两行,第一行给你由26个单个小写字母表示的变量,第二行给出成对的变量如(x,y),表示x要在y前面.然后要你输出所有可能的变量序列且满足第二行的顺序约束.如果存在多解,按字典序从小到大输出所有结果.

分析:

注意了由于这里要输出所有的合法拓扑排序序列且要求字典序从小到大输出.并且此题保证了拓扑排序一定存在,所以我们就不能用刘汝佳的那个拓扑排序方法了.

这里我们必须用DFS+回溯构造法来按字典序从小到大构造所有可能的拓扑排序.

首先本题的本质是用题目所给的字母构造一个符合要求的字母序列.这个字母需要要满足什么要求呢?

1.当前被选的字母必须有效且当前被选的字母vis=false,即还没被选

2.当我们从前到后依次选择一个字母x(且x>y)放进topo数组的时候,我们要保证在topo数组的当前位置cnt的前面那些位置中不会出现y这种字母.

3.可能有人会有疑问,就算保证了x(且z>x)出现在它的所有后继前面,但是你没有保证z出现在x前面啊,那如果已经选了x的时候还没选z,怎么能形成合法的序列呢?

解答:当选了x时还没选z的话,在之后的递归中,标记当前位置的cnt就不可能==n,所以dfs不会产生一个可行解,这个dfs就无疾而终了.也就是说程序会自动忽略这种非法解.

AC代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=30;
const int maxm=500;
int n;//有效字母数
int G[maxn][maxn];
int vis[maxn];
int ans[maxn];
int cnt;
bool mark[maxn];//标记当前字母出现在变量中
bool ok(int i,int cnt)//如果在ans[0,cnt-1]出现了一个本应在i后面才出现的字母,那么返回false
{
    for(int j=0;j<cnt;j++)
        if(G[i][ans[j]]) return false;
    return true;
}
void dfs(int cnt)
{
    if(cnt==n)
    {
        for(int i=0;i<n;i++)
            printf("%c",ans[i]+'a');
        printf("\n");
    }
    else for(int i=0;i<26;i++)if(mark[i]&&!vis[i]&&ok(i,cnt))
    {
        vis[i]=1;
        ans[cnt]=i;
        dfs(cnt+1);
        vis[i]=0;
    }
}
int main()
{
    char str[1000];
    while(gets(str))
    {
        n=0;
        memset(mark,0,sizeof(mark));
        memset(G,0,sizeof(G));
        memset(vis,0,sizeof(vis));
        for(int i=0;str[i];i++)if(str[i]!=' ')
            mark[str[i]-'a']=true, n++;
        gets(str);
        for(int i=0;str[i];i++)if(str[i]!=' ')
        {
            int a,b;
            a=str[i++]-'a';
            while(str[i]==' ')
                i++;
            b=str[i]-'a';
            G[a][b]=1;
        }
        dfs(0);//表示当前正在构造第0个位置
        puts("");
    }
    return 0;
}