五十分求助
查看原帖
五十分求助
297555
Zlc晨鑫楼主2020/9/27 07:03

不知道哪里出了问题qwq

//第一道欧拉图的题 
#include <cstdio>
#include <iostream>
using namespace std;

//并查集板子
int dad[55], t;
int anc(int x) {
	if (dad[x]!=-1) return dad[x]=anc(dad[x]);
	return x;
}
bool ask(int x, int y) {
	return anc(x)==anc(y);
}
void uni(int x, int y) {
	x=anc(x), y=anc(y);
	if (x!=y) dad[x]=y/*t--错误的写法,详情见下*/;
}

int e[55][55], du[55];

inline int turn(char x) {
	if (x>='A'&&x<='Z') return x-'A';
	else return x-'a'+26;
}

void dfs(int x) {
	if (x>=0&&x<=25) putchar(x+'A');
	else putchar(x-26+'a');
	
	for (int i=0; i<52; ++i)
		if (e[x][i]!=0)  {
			e[x][i]=0, e[i][x]=0;
			dfs(i);
		}
}

int main() {
	//注意此处要将祖先设为-1,因为'A'的下表是0 
	for (int i=0; i<52; ++i) dad[i]=-1;
	int n;
	scanf("%d", &n);
	//t=n;这个写法是错误的,因为n是边数而非结点数
	t=0; 
	for (int i=1; i<=n; ++i) {
		char a, b;
		cin>>a>>b;
		a=turn(a), b=turn(b);
		uni(a, b);
		e[a][b]=1;
		e[b][a]=1;
		du[a]++;
		du[b]++;
	}
	//计算有多少个祖先(即集合的个数) 
	for (int i=0; i<52; ++i) 
		if (du[i]&&dad[i]==-1) t++;
	if (t>1) puts("No Solution");
	else {
		int cnt=0, p=-1;
		for (int i=0; i<52; ++i)
			if (du[i]==1) cnt++, p=p==-1?i:p;
		if (cnt>2) puts("No Solution");
		else {
			if (p==-1) {
				p=0;
				while (!du[p]) p++;
			}
			dfs(p);
		}
	}
	return 0;
}
2020/9/27 07:03
加载中...