社区讨论

50分求助

P1341无序字母对参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@loc7uhwi
此快照首次捕获于
2023/10/30 09:23
2 年前
此快照最后确认于
2023/11/04 18:54
2 年前
查看原帖
求求大佬来帮我看下代码
CPP
#include<iostream>
using namespace std;

bool map[500][500];
long long n;

long long ap[500];
long long fa[500];
long long fi;
long long cnt;
char st[500];
bool fin;
long long find(long long x){
	if(fa[x]!=x)fa[x] = find(fa[x]);
	return fa[x];
}

void dfs(long long j,long long cur){
	bool all = 1;
	for(long long i = 'A';i<='z';i++){
		if(map[j][i] == 1){
			all = 0;
			map[j][i] = 0;
			map[i][j] = 0;
			st[cur] = char(j);
			dfs(i,cur+1);
			//map[j][i] = 1;
			//map[i][j] = 1;
		}
	}
	st[cur] = j;
	/*if(cur>n&&all == 1&&!fin){
		for(long long i = 1;i<cur;i++){
			cout<<st[i];
		}
		cout<<char(j)<<endl;
		fin = 1;
	}*/
}

int main(){
	cin>>n;
	for(long long i = 1;i<200;i++){
		fa[i] = i;
	}
	for(long long i = 0;i<n;i++){
		char a,b;
		cin>>a>>b;
		map[a][b] = 1;
		map[b][a] = 1;
		ap[a]++;
		ap[b]++;
		fa[find(a)] = find(b);
	}
	for(long long i = 1;i<200;i++){
		if(fi == 0&&ap[i] != 0){
			fi = find(i);
		}
		if(ap[i]!=0&&fi!=0&&fi != find(i)){
			cout<<"No Solution"<<endl;
			return 0;
		}
		if(ap[i]%2 == 1){
			cnt++;
		}
	}
	if(cnt>2){
		cout<<"No Solution"<<endl;
		return 0;
	}
	for(long long i =1;i<200;i++){
		if(ap[i]%2==1&&ap[i]!=0){
			dfs(i,1);
			for(long long i = 1;i<=n+1;i++){
				cout<<st[i];
			}
			return 0;
		}
	}
	for(long long i =1;i<200;i++){
		if(ap[i]!=0){
			dfs(i,1);
			for(long long i = 1;i<=n+1;i++){
				cout<<st[i];
			}
			return 0;
		}
	}
	cout<<"No Solution"<<endl;
	return 0;
} 

回复

0 条回复,欢迎继续交流。

正在加载回复...