46分求助!谢谢~
  • 板块P1127 词链
  • 楼主LifeDancer
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/7/31 16:25
  • 上次更新2023/10/27 17:36:34
查看原帖
46分求助!谢谢~
556337
LifeDancer楼主2022/7/31 16:25
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#define MAXN 1010

using namespace std;

struct edge {
    int to, num;
    string word;
};

string s[MAXN];
int vis[MAXN]{0};
int p[27]{0}, in[27]{0}, out[27]{0};
vector<edge> edges[MAXN];
vector<string> res;
int n, cnt_trees{0};
int Eular_start=0, Eular_end=0;

int find(int x) {
    return p[x]==x ? x : find(p[x]);
}

void union_(int x, int y) {
    p[y] = x;
}

void build_Eular_road() {
    for(int i=0; i<n; ++i) {
        int st = s[i][0]-'a'+1;
        int ed = s[i][s[i].length()-1]-'a'+1;
        ++out[st];
        ++in[ed];
        
        if(!p[st]) {
            p[st] = st;
            ++cnt_trees;
        }
        if(!p[ed]) {
            p[ed] = ed;
            ++cnt_trees;
        }
        if(st != ed && find(st) != find(ed)) {
            union_(st,ed);
            --cnt_trees;
        }
        edge e;
        e.to = ed;  e.num = i;  e.word = s[i];
        edges[st].push_back(e);
    }
}

bool judge_Eular_road() {
    if(cnt_trees != 1)  return false;
    for(int i=1; i<=26; ++i) {
        if(!p[i])  continue;
        if(out[i]-in[i] == 1) {
            if(Eular_start) return false;
            Eular_start = i;
        }
        if(in[i]-out[i] == 1) {
            if(Eular_end)   return false;
            Eular_end = i;
        }
        if(abs(in[i]-out[i]) > 1)   return false;
    }
    if((!Eular_start&&Eular_end) || (!Eular_end&&Eular_start)) 
            return false;
    if(!Eular_start)    Eular_start = s[0][0]-'a'+1;    //欧拉环路
    return true;
}

void dfs(int cnt, int u, int prev_num) {    // prev_num记录前一条边的编号
    if(cnt == n) {
        for(int i=0; i<n; ++i) {
            cout << res[i];
            --cnt;
            if(cnt>0) cout << ".";
        }
        return;
    }
    for(int i=0; i<edges[u].size(); ++i) {
        edge e = edges[u][i];
        if(!vis[e.num]) {
            vis[e.num] = 1;
            res.push_back(e.word);
            dfs(cnt+1, e.to, e.num);
            res.pop_back();
        }
    }
    vis[prev_num] = 0;  //回溯
}

int main() {
    cin >> n;
    for(int i=0; i<n; ++i)  cin >> s[i];
    sort(s, s+n);
    build_Eular_road();
    if(!judge_Eular_road()) {
        cout << "***" << endl;
        return 0;
    }
    dfs(0, Eular_start, 0);
    return 0;
}
2022/7/31 16:25
加载中...