洛谷 P1341 无序字母对(欧拉回路)

题目传送门

解题思路:

一道欧拉回路的模板题,详细定理见大佬博客,任意门

AC代码:

 #include<cstdio>
#include<iostream> using namespace std; int ans[],du[],n,k = 0x7f7f7f,b[][],cnt = 0x3f,bj,tot;
string l; inline void dfs(int x) {
for(int i = ;i < ; i++)
if(b[x][i]) {
b[x][i] = b[i][x] = ;
dfs(i);
}
ans[++tot] = x;
} int main()
{
scanf("%d",&n);
for(int i = ;i <= n; i++) {
int x,y;
cin >> l;
x = l[] - 'A';
y = l[] - 'A';
k = min(k,min(x,y));
b[x][y] = b[y][x] = ;
du[x]++;
du[y]++;
}
for(int i = ;i < ; i++)
if(du[i] % == ) {
bj++;
cnt = min(cnt,i);
}
if(bj == ) dfs(k);
else if(bj == ) dfs(cnt);
else {
printf("No Solution");
return ;
}
for(int i = tot;i >= ; i--)
printf("%c",ans[i] + 'A');
return ;
}
上一篇:apk反编译生成程序的源代码和图片、XML配置、语言资源等文件


下一篇:洛谷P1341 无序字母对【欧拉路】【dfs】