求助 wa2 本地是ac的
查看原帖
求助 wa2 本地是ac的
1156120
sa_no_pool楼主2024/3/18 16:06
#include<bits/stdc++.h>
using namespace std;
# define fi first
# define se second
# define all(x) x.begin(),x.end()
# define stst stringstream
# define pb push_back
# define pf push_front
# define fa(i,op,n) for (int i = op; i <= n; i++)
# define fb(j,op,n) for (int j = op; j >= n; j--)
# define fg(i,op,n) for (int i = op; i != n; i = ne[i])
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
const int N = 1e3,INF = 0x3f3f3f3f,mod = 1e9+7;
const LL MOD = 212370440130137957ll;//hash(hight)
const int base = 131;
const int seed=10086,mo=1e6+7; //hash(lower)
int prime = 233317;
int G[N][N];//不需要重边,所以然后直接置为0
int n;
int p[N];
int d[N];
set<int> S;
stack<char> st;
int find(int x){
	if(p[x] != x) p[x] = find(p[x]);
	return p[x]; 
}
bool merge(int a,int b){
	int fa = find(a),fb = find(b);
	if(fa != fb){
		p[fa] = fb;
		return 1;
	}
	return 0;
}
void dfs(int u){
	for(auto v:S){
		if(G[u][v]>=1){
			G[u][v] = 0;//不需要重边
			G[v][u] = 0;
			dfs(v);
		}
	}
	st.push((char)(u+65));
}
int main()
{
	//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	scanf("%d",&n);
	fa(i,0,N) p[i] = i;
	int start = 200,u = 200;
	char s[5];
	fa(i,1,n){
		scanf("%s",s);
		char c1 = s[0],c2 = s[1];
		int x = c1-'A',y = c2-'A';
		u = min({u,x,y});
		S.insert(x),S.insert(y);
		merge(x,y);
		d[x]++,d[y]++;
		G[x][y] ++,G[y][x]++;
	}
	int f = find(u);
	int cnt = 0;
	for(auto v:S){
		if(find(v) != f){
			cout<<"No Solution"<<'\n';
			return 0;
		}
		if(d[v]%2){
			cnt++;
			start = min(v,start);
		}
	}
	if(cnt>2){
		cout<<"No Solution"<<'\n';
		return 0;
	}
	dfs(start);
	while(st.size()){
		cout<<st.top();
		st.pop();
	}	
	return 0;
}
2024/3/18 16:06
加载中...