POJ 1270 Following Orders（拓扑排序）

题意：给两行字符串，第一行为一组变量，第二行时一组约束（每个约束包含两个变量，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;

	}

}

巴特西

POJ 1270 Following Orders（拓扑排序）

最新文章

热门文章