题目链接：http://poj.org/problem?id=1270
题目大意：给定一系列字符串， 再给出两两先后顺序，按字典序输出整个字符串所有可能的排序 如 a b g f \n a b b f 表示 a必须在b前面 b必须在f前面 其他的任意
思路：看了解题报告，想了好一会儿，原因在于之前对dfs理解的还不够透彻。本题是DFS中包含了拓扑排序的相关入度计算，每次只要把入度为0的点加入路径中，并改变其影响的那个店，最后输出路径即可。总之，第一次做dfs和top相结合的题目，认真理解，收获挺大的。
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
int degree[21];//每个顶点的入度
bool visited[21];
int nvertices;
char ver[21];
bool graph[21][21];
map<char,int>id;//字母与编号的映射
char route[21];//深度遍历过程中存储路径
int num;//当前路径中的顶点数
void dfstopsort() //DFS 中包含top排序的入度判断
{
if(num==nvertices)
{
cout<<route<<endl;
return;
}
int i,j;
for(i=1;i<=nvertices;i++)
{
if(degree[i]==0 && !visited[i])
{
route[num++] = ver[i-1]; //将入度为0的顶点加入路径中
visited[i]=1; //标记该店已经被访问
for(j=1;j<=nvertices;j++)
{
if(graph[i][j])
degree[j]--;
}
dfstopsort(); //写在递归后面的都表示DFS在回退时应该进行的 本题要还原变量
num--;
visited[i]=0;;
for(j=1;j<=nvertices;j++)
{
if(graph[i][j])
degree[j]++;
}
}
}
}
int main()
{
char a[50];
while(gets(a))
{
memset(graph,0,sizeof(graph));
memset(degree,0,sizeof(degree));
int i,len,j=0;
len = strlen(a);
for(i=0;i<len;i++)
{
if(a[i]>='a' && a[i]<='z') //要判断是因为有空格
ver[j++] = a[i];
}
nvertices = j;
sort(ver,ver+j); //按字母排好序 这样才能按字典序输出
for(i=0;i<j;i++)
id[ver[i]] = i+1;
char b[50];
gets(b);
len = strlen(b);
int c = 0; //c的作用是标记是第一个字符还是第二个字符
char ch1,ch2;
for(i=0;i<len;i++)
{
if(b[i]>='a' && b[i]<='z')
{
if(c==0)
{
ch1 = b[i];
c=1;
}
else
{
ch2 = b[i];
c =0;
degree[id[ch2]]++;
graph[id[ch1]][id[ch2]] = 1;
}
}
}
num = 0;
memset(route,0,sizeof(route));
memset(visited,0,sizeof(visited)); //visited初始化应该放在dfs外面
dfstopsort();
cout<<endl;
}
return 0;
}