{
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;
}
方法2: 利用STL库里面的next_permutation()函数，把所有的字符串全排列都找出
把符合情况的字符串输出，不符合的舍去
[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
int Topsort(char ch[])
{
int i,j;
for(i=n-1;i>0;i--)
{
for(j=i-1;j>=0;j--)
{
if(edge[zm[ch[i]-'a']][zm[ch[j]-'a']]==1)
return 0;
}
}
return 1;
}
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];
}
ch1[n]='\0';
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']]++;
}
if(Topsort(ch1)) //符合限制条件则输出
printf("%s\n",ch1);
while(next_permutation(ch1,ch1+n))
{
if(Topsort(ch1)) //符合限制条件则输出
printf("%s\n",ch1);
}
// printf("\n");
}
return 0;
}