30pts求调必关
  • 板块P1127 词链
  • 楼主I_Love_Codm
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/7/30 23:00
  • 上次更新2025/7/31 13:19:31
查看原帖
30pts求调必关
1436267
I_Love_Codm楼主2025/7/30 23:00
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

string s[N];
vector<int> g[N];
stack<string> ans;
bool flg = 0, vis[N];
int n, st = -1, ed = -1, in[N], out[N], cnt_st = 0, cnt_ed = 0;;

void dfs(int u) {
    for (int &v: g[u]) {
        if (vis[v]) continue;
        vis[v] = 1;
        dfs(v);
    }

    ans.push(s[u]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> s[i];
    sort(s + 1, s + n + 1);

    for (int i = 1; i <= n; i++) {
        char c = s[i].back();
        for (int j = 1; j <= n; j++) {
            if (i != j && s[j][0] == c) {
                g[i].push_back(j);
                out[i]++;
                in[j]++;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        int d = out[i] - in[i];
        if (d == 1) st = i, cnt_st++;
        else if (d == -1) ed = i, cnt_ed++;
        else if (d) {
            cout << "***";
            return 0;
        }
    }

    if (!((!cnt_st && !cnt_ed) || (cnt_st == 1 && cnt_ed == 1))) {
        cout << "***";
        return 0;
    }

    st = max(st, 1);
    memset(vis, 0, sizeof(vis));
    vis[st] = 1;
    dfs(st);

    if (ans.size() != n) {
    	cout << "***";
        return 0;
	}

	flg = 0;
	while (ans.size()) {
		if (flg) cout << '.';
		else flg = 1;
		cout << ans.top();
		ans.pop();
	}
    return 0;
}

2025/7/30 23:00
加载中...