poj1270_toposort+回溯-白红宇

poj1270_toposort+回溯

阅读量：4326 次

发布时间：2019-06-06

本文共 1223 字，大约阅读时间需要 4 分钟。

题意：给定一串字符（互异），再给出一个字符序列，表示一种前后关系，如abefcd,表示a<b,e<f,c<d。

将开始给出的字符进行排序，使之符合这个关系序列。并按字典序输出这些符合要求的字符序列。例如：

a b f g

a b b f 结果是：

abfg

abgf

agbf

gabf

分析：这题就是一个给定部分顺序，来确定整体顺序的拓扑排序。但一般的拓扑排序只找出一种符合要求的序列，这题要求找出所有符合要求的序列，这就有点困难，所以还得加上回溯算法。最后对求出的所有符合要求的序列进行排序输出就可以了。

代码：

每次写递归都TM有种向吐血的赶脚!!!

View Code

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include
          5 #include 
          
            6 using namespace std; 7 //toposort+回溯 8 //188K 16MS 9 const int maxnum=26;10 bool graph[maxnum][maxnum];11 int indegree[maxnum];12 char str[maxnum];13 char ans[maxnum];14 map
           
            hash;15 int res;16 17 void toposort(int depth)18 {19 if(depth==res)20 {21 printf("%s\n",ans);22 return;23 }24 int i,j;25 for(i=0;i
            
             ='a' && temp[i]<='z')56 {57 str[k++]=temp[i];58 }59 sort(str,str+k); //这样保证按字典顺序输出60 res=k; //这里弄错了61 for(i=0;i
             
              ='a'&&temp[i]<='z')68 {69 if(flag==0)70 {71 c1=temp[i];72 flag=1;73 }74 else75 {76 c2=temp[i];77 graph[hash[c1]][hash[c2]]=true;78 indegree[hash[c2]]++;79 flag=0;80 }81 }82 memset(ans,0,sizeof(ans));//这里一开始没加，wa了83 toposort(0);84 printf("\n");85 }86 return 0;87 }

转载于:https://www.cnblogs.com/pushing-my-way/archive/2012/08/23/2652588.html

你可能感兴趣的文章