题意: 给两行字符串,第一行为一组变量,第二行时一组约束(每个约束包含两个变量,x y 表示 x <y)。输出满足约束的所有字符串序列。
思路:拓扑排序 + 深度优先搜索(DFS算法)
课本代码:
#include<iostream>
#include<cstring>
#include<string>
using namespace std; int n;
int pre[300]; // 存字母入度// 把小写字母的ascii码都包括在内
bool has[300];//节点标志 // 把小写字母的ascii码都包括在内
string var,v;
void dfs(int dep,string res){
if(dep==n+1){ //第n+1个字母不用找(即找完n个字母时结束)
cout<<res<<endl;
return ;
}
for(int i='a';i<='z';i++)//按字典顺序遍历查找入度为0的节点,释放该节点
if(has[i] &&pre[i]==0){
has[i]=false;//删除点
int k;
for(k=0;k<v.length();k+=4)//删除该节点的所有出边
if(v[k]==i) --pre[v[k+2]];
dfs(dep+1,res+char(i));
for(k=0;k<v.length();k+=4)//恢复被删边
if(v[k]==i) ++pre[v[k+2]];
has[i]=true;//恢复点
}
} int main()
{
while(getline(cin,var) &&getline(cin,v))
{
memset(pre,0,sizeof(pre));//初始化节点标志
memset(has,0,sizeof(has));//初始化节点入度
int i;
for(i=0;i<var.length();i+=2)//初始节点标志
has[var[i]]=true;
n=var.length()/2 +1;
for(i=0;i<v.length();i+=4)//统计节点入度
++pre[v[i+2]];
dfs(1,"");
cout<<endl;
}
}