演算法分析

Copyright ? 2019 ctjcalc，轉載請注明URL，并給出原文鏈接，謝謝，其實這道題并不難，關鍵是如何轉化，因為需要找到最長的單詞接龍，就可以用圖論來看，單詞接龍不會出現環，所以，這就是個`DAG`上的拓撲排序，如果兩個單詞可以接在一起，就必須滿足以下條件：

前一個單詞的字母都必須在后一個單詞中出現過
任意一個字母都不能少
后一個單詞的長度比前一個單詞多1，不能多也不能少

因為沒有對順序作要求，我們只需記錄其出現次數即可，并存盤它們的哈希值（hash/散列），列舉每個字串的每個字母，增加其出現次數，并判斷該字串是否存在，如果存在，就建一條有向邊，

最后，拓撲排序，記錄答案并通過前驅指標遞回輸出，

#include <bits/stdc++.h>
using namespace std;

#if __cplusplus < 201103 || !defined(__cplusplus)
typedef map<int,int> maptype;
#else
typedef unordered_map<int,int> maptype; // 如果是C++11及以上，使用無序哈希映射
#endif

struct edge
{
    int to,nxt;
};

edge e[1000001]; int head[10001],tot;
int in[10001];
maptype mapping;
char str[10001][105];
int len[10001];
int cnt[10001][26];
int f[10001];
int pre[10001];
int n;

void connect(int x,int y){
    e[++tot]=(edge){y,head[x]}; head[x]=tot; ++in[y];
}

int gethash(int idx){ // 哈希函式
    int val=0;
    for(register int i=0;i<26;++i){
        val=val*23+cnt[idx][i];
    }
    return val;
}

void output(int d){ // 遞回輸出
    if(pre[d]!=0){
        output(pre[d]);
    }
    printf("%s\n",str[d]+1);
}

void topology(){ //拓撲排序
    queue<int> q;
    for(register int i=1;i<=n;++i){
        if(!in[i]) q.push(i);
        f[i]=1;
    }
    while(!q.empty()){
        int x=q.front(); q.pop();
        for(register int i=head[x],y;y=e[i].to,i;i=e[i].nxt){
            if(f[y]<f[x]+1){
                f[y]=f[x]+1;
                pre[y]=x;
            }
            if(--in[y]==0){
                q.push(y);
            }
        }
    }
    int ans=0;
    for(register int i=1;i<=n;++i){
        if(f[ans]<f[i]){
            ans=i;
        }
    }
    printf("%d\n",f[ans]);
    output(ans);
}

void build(){ //建邊
    for(register int i=1;i<=n;++i){
        for(register int j=0;j<26;++j){
            ++cnt[i][j];
            int h=gethash(i);
            if(mapping.find(h)!=mapping.end()){ // 如果存在一個可接的單詞就建邊
                connect(i,mapping[h]);
            }
            --cnt[i][j]; // 要記得還原
        }
    }
}

void input(){
    while(scanf("%s",str[++n]+1)!=EOF); --n; // 注意輸入
    for(register int i=1;i<=n;++i){
        len[i]=strlen(str[i]+1);
        for(register int j=1;j<=len[i];++j){
            ++cnt[i][str[i][j]-'a'];
        }
        mapping[gethash(i)]=i;
    }
}

int main(){
    input();
    build();
    topology();
    return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137726.html

標籤：其他

上一篇：演算法導論之眼前一亮（持續更新）

下一篇：【資料結構】線段樹詳解

【題解】游戲

演算法分析