http://poj.org/problem?id=1270
题意：给一个字符串，然后再给你一些规则，要你把所有的情况都按照字典序进行输出。
思路：很明显这肯定要用到拓扑排序，当然看到discuss里面有些人有bfs也可以做，有时候觉得搜索只要剪枝剪的好，啥都可以用搜索。
因为我也不是很会拓扑排序，所以在找这类的题来练习，增加对其的理解。我就发现了一个问题，为什么拓扑排序要构图？
其实也很简单，因为拓扑排序是对一个有向的无环图进行排序，有向指的是某个点排序后一定是出现在他的前一个点的后面。这个是一定的，所以要构图。
当然，我现在也只是浅显的理解。以后有了更深的理解会在写。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <map>
#define maxn 60 using namespace std; int indegree[ maxn ];
char ans[ maxn ];
int graph[ maxn ][ maxn ],num;
char str[ maxn ]; int cmp(const void *a,const void *b)
{
return (*(char *)a)-(*(char * )b);
} void toposort(int depth) //toposort+递归.
{
if(depth == num )
{
printf("%s\n",ans);
return;
}
for( int i = ; i < num ; i++)
{
if(!indegree[ i ])
{
indegree [ i ] --;
ans[ depth ] = str[ i ];
for ( int j = ; j < num ; j++ )
if( graph [ i ][ j ])
indegree[ j ] --;
toposort(depth+);
indegree [ i ] ++;
for( int j = ; j < num ; j++ )
if(graph[ i ][ j ])
indegree [ j ] ++;
}
}
} int main()
{
// freopen("in.txt","r",stdin);
char inp[ maxn ];
while(gets( inp ))
{
memset( graph , , sizeof( graph ) );
memset( str , , sizeof( str ) );
memset( ans , , sizeof( ans ) );
memset( indegree , , sizeof( indegree ) );
map<char,int >s;
int len = strlen( inp ), k = ;
for( int i = ; i < len ; i++ )
if(inp[ i ] >='a' && inp[ i ] <= 'z')
str[ k++ ] = inp[i];
qsort( str , k , sizeof( str[] ) , cmp );
num = k;
for( int i = ; i < len ; i++ )
s[ str[ i ] ] = i; //对点进行构图一定要在排序之后，不然会wa.
memset( inp , , sizeof( inp ) );
gets( inp );
len = strlen( inp );
for( int i = ; i < len ; i += )
{
graph[ s[ inp[ i ] ] ][ s[ inp[ i + ] ] ] = ;
indegree [ s[ inp[ i + ] ] ] ++;
}
toposort();
memset( inp , ,sizeof( inp ) );
printf("\n");
}
return ;
}