poj 2337 && zoj 1919 欧拉回路+连通性判断

题目要求按字典序排列，而且可能有重边

所以一开始就将数组从大到小排列，那么我将字符串加入链表时就会令小的不断前移，大的被挤到后面

这里有一点问题就是我一开始使用的是qsort：

int cmp(const void *s1 , const void *s2)
{
return strcmp((char*)s1 , (char*)s2)<0;
}

qsort(str , n , sizeof(str[0]) , cmp)

poj一直wa，试了发zoj却过了，可能是编译器原因吧，然后将字符串放入了结构体重新进行排序，poj才给过

寻找欧拉回路的关键代码

void dfs(int u , int id)
{
    for(int i=first[u] ; i!=-1 ; i=e[i].next){
        if(e[i].flag){
            e[i].flag=false;
            dfs(e[i].y , e[i].id);
            rec[top2++]=e[i].id;
        }
    }
}

将其逆序输出即可

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define N 1010

 int n , in[N] , out[N] , cnt , st , la;

 int first[N] , k;

 int top1 , top2;

 int rec[N];

 struct Str{

     char str[];

 }str[N];

 bool cmp(Str s1 , Str s2)

 {

     return strcmp(s1.str , s2.str)>;

 }

 struct Edge{

     int y , next , id;

     bool flag;

 }e[N*];

 Edge stack[N];

 void add_edge(int x,int y ,int id)

 {

     e[k].y=y , e[k].id = id , e[k].flag=true , e[k].next=first[x];

     first[x]=k++;

 }

 void dfs(int u , int id)

 {

     for(int i=first[u] ; i!=- ; i=e[i].next){

         if(e[i].flag){

             e[i].flag=false;

             dfs(e[i].y , e[i].id);

             rec[top2++]=e[i].id;

         }

     }

 }

 void Fleury()

 {

     top1 = top2 = ;

     dfs(st , -);

 }

 int main()

 {

   //  freopen("a.in" , "r" , stdin);

     int T;

     scanf("%d" , &T);

     while(T--)

     {

         scanf("%d" , &n);

         for(int i= ; i<n ; i++) scanf("%s" , str[i].str);

         sort(str , str+n , cmp);

      //   for(int i=0 ; i<n ; i++) printf("%s\n" , str[i]);

         memset(first , - , sizeof(first));

         memset(in ,  , sizeof(in));

         memset(out ,  , sizeof(out));

         k=;

         for(int i= ; i<n ; i++){

             int len = strlen(str[i].str);

             int a = str[i].str[]-'a' , b = str[i].str[len-]-'a';

             add_edge(a , b , i);

             in[b]++ , out[a]++;

         }

         cnt=,st=- , la=-;

         bool flag=true;

         for(int i=;i<;i++){

             if(abs(out[i]-in[i])>){

                 flag=false;

                 break;

             }

             if(out[i]!=in[i]){

                 cnt++;

                 if(st==- && out[i]==in[i]+) st=i;

                 else if(la==- && in[i]==out[i]+) la=i;

                 else{

                     flag=false;

                     break;

                 }

             }

         }

         if(!flag || (cnt!= && cnt!=)){printf("***\n");continue;}

         if(st<){

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

                 if(out[i]){

                     st = i;

                     break;

                 }

         }

         Fleury();

            // cout<<top2<<endl;

         if(top2<n){printf("***\n");continue;}

         for(int i=top2- ; i> ; i--) printf("%s." , str[rec[i]].str);

         printf("%s\n" , str[rec[]].str);

     }

     return ;

 }

巴特西

poj 2337 && zoj 1919 欧拉回路+连通性判断

最新文章

热门文章