30pts 求调
查看原帖
30pts 求调
591561
Xianzi_楼主2024/12/19 17:53
#include "bits/stdc++.h"
using namespace std;
int n, st, cnt, len, minn = 0x3f3f3f3f, root;
int f[3005], ans[3005];
bool flag;
bool vis[3005];
vector <int> g[55];
int char_to_int(char ch) {
	if (ch >= 'A' && ch <= 'Z') return int(ch - 'A' + 1);
	if (ch >= 'a' && ch <= 'z') return int(ch - 'a' + 27);
	return -1;
}
char int_to_char(int k) {
	if (k >= 1 && k <= 26) return char(k + 'A' - 1);
	if (k >= 27 && k <= 52) return char(k + 'a' - 27);
	return -1;
}
void init() {
	for (int i = 1; i <= n; i++) 
		f[i] = i;
}
int find(int x) {
	if (x == f[x]) return x;
	else return f[x] = find(f[x]);
}
void Union(int a, int b) {
	int u = find(a), v = find(b);
	int donk_666 = rand();
	if (donk_666 % 2) f[u] = v;
	else f[v] = u;
}
void dfs(int u) {
	for (int i = 0; i < g[u].size(); i++) {
		if (g[u][i] == 0) continue;
		int v = g[u][i]; g[u][i] = 0;
		for (int j = 0; j < g[v].size(); j++) 
			if (g[v][i] == u) g[v][j] = 0;
		dfs(v);
	}
	ans[++len] = u;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	srand(time(0));
	cin >> n;
	init();
	for (int i = 1; i <= n; i++) {
		char a, b;
		cin >> a >> b;
		int u = char_to_int(a), v = char_to_int(b);
		// cout << u << " " << v << "\n";
		g[u].push_back(v), g[v].push_back(u);
		Union(u, v);
		vis[u] = vis[v] = 1;
	}
	for (int i = 1; i <= 125; i++) {
		if (minn == 0x3f3f3f3f && vis[i] == 1) 
			minn = i, root = find(i);
		if (vis[i] == 1 && g[i].size()) 
			sort(g[i].begin(), g[i].end());
		if (vis[i] == 1 && g[i].size() == 0) 
			{cout << "No Solution" << "\n"; exit(0);}
		else if (vis[i] == 1 && g[i].size() % 2 == 1) {
			cnt++;
			if (st == 0) st = i;
		}
	}
	if (cnt > 2) {cout << "No Solution" << "\n"; exit(0);}
	else if (cnt == 0) dfs(minn);
	else if (cnt == 2) dfs(st);
	for (int i = len; i >= 1; i--) cout << int_to_char(ans[i]);
	cout << "\n";
	return 0;
}
2024/12/19 17:53
加载中...