P1127 词链题解

loc_equinox · 2020-07-24 22:28:12 · 题解

说在前面的话：

在我写这篇题解时，因为数据太水问题，过审的多数题解都可以被 Hack，带来了许多困扰。所以希望这篇文章能给大家带来帮助。

（欢迎各位大佬~~Hack~~指正）

进入正题：

读题，容易想到的是以单词为点，通过末字母与首字母比较来连边，最后 DFS 寻找字典序最小的词链。这里因为要求“字典序最小”，所以要先排序。

但是这么写的缺点就在于，起始点是不确定的，所以要挨个找起点就十分低效。写出来了也会有两个点超时。

于是想到题目所求词链的特征：“单词在词链中出现且仅出现一次”。联想到欧拉路的特征，也是经过图的每一条边且只经过一次。所以考虑构造一张图，寻找其欧拉路（这里包括欧拉通路和欧拉回路）。

构造图的时候，以单词为有向边，字母为顶点。比如单词 abc，就是从顶点 a 指向顶点 c 的边之一。当一个单词的首末字母相同时，它就是一个自环。建图完毕后，先判断是否存在欧拉路，再 DFS 寻找字典序最小的欧拉路。

接下来分析代码：

Part 1:读入，建图

在建边的同时并查集，最后判断集合个数是不是 1，即判断所有点是不是都在一个集合内。这也是第一次判断欧拉路是否存在。

//注意：这只是部分代码
int n,i,letter[27],in[27],out[27],fa[27],set_count;
string s[1002];
int ch_start,ch_end,stf,edf;
vector<vector<node> >E;
bool cmp(string a,string b)
{
    return a<b;
}
int find(int x)
{
    if(fa[x]!=x)return fa[x]=find(fa[x]);
    return fa[x];
}
void unionn(int x,int y)
{
    fa[y]=x;
    return;
}
struct node
{
    int to,ord;
    string word;
};
int main()
{
    cin>>n;
    E.resize(27);//E数组存边
    for(i=1;i<=n;i++)cin>>s[i];
    sort(s+1,s+n+1,cmp);//排序
    for(i=1;i<=n;i++)
    {
        ch_start=s[i][0]-'a'+1;//第i个词的首字母
        ch_end=s[i][s[i].length()-1]-'a'+1;//第i个词的末字母
        out[ch_start]++;//首字母出度加1
        in[ch_end]++;//末字母入度加1
        if(!letter[ch_start])//如果这个首字母（节点）没有出现过
        {
            set_count++;//集合数加1
            letter[ch_start]=1;//标记一下
            fa[ch_start]=ch_start;//并查集初始化
        }
        if(!letter[ch_end])//同上
        {
            set_count++;
            letter[ch_end]=1;
            fa[ch_end]=ch_end;
        }
        if(ch_start!=ch_end)//如果不是自环
        {
            stf=find(ch_start);
            edf=find(ch_end);
            //找代表元
            if(stf!=edf)//如果不在同一集合内
            {
                set_count--;//集合数减1
                unionn(stf,edf);
            }
        }
        node tmp;//新建一条边
        tmp.to=ch_end;
        tmp.ord=i;
        tmp.word=s[i];
        E[ch_start].push_back(tmp);//vector存图
    }
    if(set_count!=1)//如果存在多个集合（连通块），那么一定没有欧拉路
    {
        cout<<"***";
        return 0;
    }

Part 2:寻找欧拉路起始点

有向图中欧拉通路存在条件是：有且仅有一个点出度比入度大 1（起点），有且仅有一个点入度比出度大 1（终点），其余点入度等于出度。

有向图中欧拉回路存在条件是：所有点入度等于出度。

结合上述判定方法，有如下代码：

int Eular_start,Eular_end;
//...
    for(i=1;i<=26;i++)//最多只有26个点
    {
        if(!letter[i])continue;//如果这个字母没有出现就跳过
        if(out[i]==in[i]+1)//这个点出度比入度大1
        {
            if(Eular_start)//如果有多个起点，那么无解
            {
                cout<<"***";
                return 0;
            }
            Eular_start=i;//标记起点
        }
        else if(in[i]==out[i]+1)//同上
        {
            if(Eular_end)
            {
                cout<<"***";
                return 0;
            }
            Eular_end=i;
        }
        else if(in[i]==out[i])continue;
        else
        {
            cout<<"***";
            return 0;
        }
    }
    if((Eular_start&&!Eular_end)||(!Eular_start&&Eular_end))//如果“有始无终”或“有终无始”，则无解
    {
        cout<<"***";
        return 0;
    }
    if(!Eular_start)Eular_start=s[1][0]-'a'+1;//如果是回路（无起点），则选字典序最小的点出发

Part 3:DFS求欧拉路

因为每个点出边已经排好了序，所以顺序遍历即可。在搜索时顺便记录答案。

int vis[1002];
string res[1002];
void dfs(int st,int now,int pre_edge)//st表示词链中有几个单词，now表示现在到达了哪一个点,pre_edge表示上一条边的序号，方便回溯
{
    if(st==n)//如果到达终点
    {
        for(i=1;i<=n;i++)//输出结果
        {
            cout<<res[i];
            if(i<n)cout<<".";
        }
        exit(0);
    }
    for(int k=0;k<E[now].size();k++)
    {
        if(!vis[E[now][k].ord])//如果未被标记过
        {
            vis[E[now][k].ord]=1;
            res[st+1]=E[now][k].word;
            dfs(st+1,E[now][k].to,E[now][k].ord);
        }
    }
    vis[pre_edge]=0;//回溯
    return;
}
//...
    dfs(0,Eular_start,0);//从Part 2中找到的起点开始

（完整代码在这里）

P1127 词链 题解