nyoj 单词拼接（并查集判断连通性+欧拉路径） - c++编程基础

TOP

nyoj 单词拼接（并查集判断连通性+欧拉路径）

2015-07-20 17:48:21 来源: 作者: 【大中小】浏览:1次

Tags：nyoj 单词拼接查集判断通性路径

这题还是比较难的。

首先建图方面，如果单纯的把单词作为点，能拼接的关系作为边，那么就是哈密顿图（每个点仅能走一次），难度比较大。

换一种思路，就是把每个单词看成一条有向边，由该单词的首字母指向尾字母。

那么这题便是欧拉图的问题了。

本质上采用的还是搜索，但是为了快速得到字典序最小的欧拉路径，首先要对单词集进行排序。

排完序后，用边集数组存图；再通过计算各点的出度与入度，同时判断基图（不考虑边的方向的图）的连通性，判断是否存在欧拉回路或欧拉通路。

如果存在欧拉回路，那么就从0开始搜索；

如果存在欧拉通路，那么就从“出度=入度+1”的点开始搜索。

参考代码如下：

边集数组存图+并查集判断连通性

 
#include
  
   
using namespace std;
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              struct Enode{ int u; int v; string s; }; Enode edge[1010]; string s[1010]; int n,m,fa[1010]; int flag[1010]; int path[1010]; int visit[1010]; int root(int x) { if (fa[x]==x) return x; return fa[x]=root(fa[x]); } void uset(int x,int y) { int a=root(x); int b=root(y); if (a!=b) fa[b]=a; } //并查集判断连通性 int judge() { int t=0; for (int i=0;i<26;++i) if (flag[i] && fa[i]==i) t++; return t == 1; } void find(int u) { for (int i=0;i
             
              > T; while (T--) { memset(visit,0,sizeof(visit)); memset(flag,0,sizeof(flag)); // memset(edge,0,sizeof(edge)); memset(path,0,sizeof(path)); memset(fa,0,sizeof(fa)); cin >> n; int i; for (i=0;i
              
               > s[i]; } sort(s,s+n); for (i=0;i<26;++i) fa[i]=i; int in[30],out[30]; memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); for (i=0;i
               
                0;--i) cout << edge[path[i]].s << "."; cout << edge[path[0]].s << endl; } else cout << "***" << endl; } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu 4771 求一点遍历所有给定点的..	下一篇：hdu4772 坐标旋转

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: