程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> nyoj 單詞拼接（並查集判斷連通性+歐拉路徑）

nyoj 單詞拼接（並查集判斷連通性+歐拉路徑）

編輯：C++入門知識

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;i0;--i)
                 cout << edge[path[i]].s << ".";
             cout << edge[path[0]].s << endl;
             }
             
             else cout << "***" << endl;
                       
          }
    return 0;
}