http://poj.org/problem?id=1270

题目大意：

给你一串序列，然后再给你他们部分的大小，要求你输出他们从小到大的所有排列。

如a b f g 然后 a<b ,b< f 那么符合要求的有abfg   abgf    agbf  gabf（即不能出现（a在b后面，b在f后面）

思路：

把这些字符看成点，如果存在a<b的关系，则在有向图中建立一条边 v(a,b)，然后进行拓扑排序。

话说这题的输入很坑爹，那个大小关系的我还以为是4个一组。。结果被坑死了。看了discuss改了才过。。第一次写拓扑。。。。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int MAXN=30;

char a[MAXN];

char temp[200];

int map[MAXN][MAXN];

bool vis[MAXN];

int id[MAXN],to[MAXN],route[MAXN];

int len;

void topsort(int cur)

{

	if(cur==len)

	{

		for(int i=0;i<len;i++)

			printf("%c",a[ route[i] ]);

		printf("\n");

		return;

	}

	for(int i=0;i<len;i++)

	{

		if(!vis[i] && !to[i])

		{

			for(int j=0;j<len;j++)     //与之相连的度减1

				if(map[i][j])

					to[j]--;

			vis[i]=true;

			route[cur]=i;

			topsort( cur+1 );

			for(int j=0;j<len;j++)

				if(map[i][j])

					to[j]++;

			vis[i]=false;

		}

	}

}

int main()

{

	int kase=0;

	while(gets(temp)!=NULL)

	{

		if(kase)

			printf("\n");

		kase++;

		memset(id,-1,sizeof(id));

		memset(map,0,sizeof(map));

		memset(vis,0,sizeof(vis));

		memset(to,0,sizeof(to));

		len=0;

		for(int i=0;temp[i]!='\0';i++)

			if(temp[i] !=' ')

				a[len++]=temp[i];

		sort(a,a+len);

		for(int i=0;i<len;i++)         //进行编号，当然你也可以直接用STL的map

			id[ a[i]-'a']=i;

		gets(temp);

		bool flag=0;

		int x;

		for (int i = 0; temp[i]!='\0'; i++)  //建立图不是i+4就好，狂WA，后看DISCUSS，跟着改了就AC了

		{

			if (temp[i] == ' ')

				continue;

			if (!flag)

				x =temp[i] - 'a';

			else

			{

				map[ id[ x ] ][ id[ temp[i]-'a'] ]=1;

				to[ id[temp[i]-'a']]++;

			}

			flag = !flag;

		}

		topsort(0);

	}

	return 0;

}