题目大意: 第一行给出字符串(小写字母)，表示出现的字符类型
第二行是约束关系，a1 b1 a2 b2 a3 b3.....ai bi，表示ai必须在bi前面
按照字典序输出所有满足约束条件的序列
如:
y z x
x z
xyz
xzy
yxz
解题思路: 题目要求字典序输出，先把给出第一行字符串排序
所有的约束条件变成有向图的边，x z表示顶点x到顶点z的边
序列的情况是否跟有向图有冲突，不冲突则正确，否则舍去
用深搜把所有满足的情况都搜索一边
每次找到入度为0的顶点就开始进入下一层，存入a[len]，并且把与这个顶点相连的点的入度都减1
直到搜索到的层数len等于字符串的长度，就输出a[ ]
也就是在搜索过程中融合拓扑排序的思想，直到不存在入度为0的顶点为止
剪枝: 把字符串转换成数字可以大大提高效率，如y z x 转换为 2 3 1
代码:
[cpp]
#include
#include
#include
#include
#include
using namespace std;
#define MAX 200
char ch1[MAX],ch2[MAX],ch3[MAX];
int n,m,zm[MAX],edge[MAX][MAX],to[MAX],visit[MAX],a[MAX];
bool comp(char a,char b)
{
return a
void DFS(int len)
{
int i,j;
if(len==n) //层数等于字符串长度则输出
{
for(i=0;i
printf("%c",ch1[a[i]]);
}
printf("\n");
return ;
}
for(i=0;i
if(!visit[i]&&!to[i])
{
for(j=0;j
if(edge[i][j]==1)
{
to[j]--;
}
}
visit[i]=1; //标记此点访问过
a[len]=i;
DFS(len+1);
for(j=0;j
if(edge[i][j]==1)
{
to[j]++;
}
}
visit[i]=0; //还原现场
}
}
return ;
}
int main()
{
int i,k,pd=0;
while(gets(ch3))
{
if(pd==0)
pd=1;
else
printf("\n"); //测试用例之间输出空行
gets(ch2);
memset(zm,-1,sizeof(zm));
memset(edge,-1,sizeof(edge));
memset(to,0,sizeof(to));
memset(visit,0,sizeof(visit));
for(i=0,n=0;ch3[i]!='\0';i++) //去除空格
{
if(ch3[i]==' ')
continue;
ch1[n++]=ch3[i];
}
sort(ch1,ch1+n,comp); //排序
for(i=0;i
zm[ch1[i]-'a']=i;
}
for(i=0,k=0;ch2[i]!='\0';i+=4) //字符串2处理,构建有向图
{
edge[zm[ch2[i]-'a']][zm[ch2[i+2]-'a']]=1;
to[zm[ch2[i+2]-'a']]++; //顶点入度+1
}
DFS(0);
// printf("\n"); 这样输出空行poj可以过,UVA会WA
}
return 0;
}
#include
#include
#include
#include
#include
using namespace std;
#define MAX 200
char ch1[MAX],ch2[MAX],ch3[MAX];
int n,m,zm[MAX],edge[MAX][MAX],to[MAX],visit[MAX],a[MAX];
bool comp(char a,char b)
{
return a
void DFS(int len)
{
int i,j;
if(len==n) //层数等于字符串长度则输出
{
for(i=0;i
printf("%c",ch1[a[i]]);
}
printf("\n");
return ;
}
for(i=0;i
if(!visit[i]&&!to[i])
{
for(j=0;j
if(edge[i][j]==1)
{
to[j]--;
}
}
visit[i]=1; //标记此点访问过
a[len]=i;
DFS(len+1);
for(j=0;j
if(edge[i][j]==