題目大意: 第一行給出字符串(小寫字母)，表示出現的字符類型
第二行是約束關系，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 <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdlib.h>
#include <algorithm>
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<b;
}
void DFS(int len)
{
int i,j;
if(len==n) //層數等於字符串長度則輸出
{
for(i=0;i<n;i++)
{
printf("%c",ch1[a[i]]);
}
printf("\n");
return ;
}
for(i=0;i<n;i++)
{
if(!visit[i]&&!to[i])
{
for(j=0;j<n;j++) //把與這個頂點相連的點入度減1
{
if(edge[i][j]==1)
{
to[j]--;
}
}
visit[i]=1; //標記此點訪問過
a[len]=i;
DFS(len+1);
for(j=0;j<n;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<n;i++) //字符串1處理,把字母轉化成0到n-1的邊
{
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 <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdlib.h>
#include <algorithm>
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<b;
}
void DFS(int len)
{
int i,j;
if(len==n) //層數等於字符串長度則輸出
{
for(i=0;i<n;i++)
{
printf("%c",ch1[a[i]]);
}
printf("\n");
return ;
}
for(i=0;i<n;i++)
{
if(!visit[i]&&!to[i])
{
for(j=0;j<n;j++) //把與這個頂點相連的點入度減1
{
if(edge[i][j]==1)
{
to[j]--;
}
}
visit[i]=1; //標記此點訪問過
a[len]=i;
DFS(len+1);
for(j=0;j<n;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<n;i++) //字符串1處理,把字母轉化成0到n-1的邊
{
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 <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdlib.h>
#include <algorithm>
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<b;
}
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<n;i++) //字符串1處理,把字母轉化成0到n-1的邊
{
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;
}
