luogu P1341 无序字母对

找欧拉回路 / 路径。

欧拉回路存在的条件是只有度数为偶数的节点，起点是字典序最小的节点

欧拉路径存在的条件是有且仅有2个度数为奇数的节点，起点是字典序最小的且度数为奇数的节点

从起点开始dfs，每次找与他相连的字典序最小的节点即可。。。回溯的时候记一下路径。。

别忘了用并茶几盘一下图是否联通。。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,t[250][250],du[250],fa[250],num;
char op[3],ans[3010];
int get(int x){return x==fa[x] ? x : fa[x]=get(fa[x]);}
void dfs(int x){
    for(int i=0;i<=230;i++){
        if(t[x][i]){
            t[x][i]=t[i][x]=0;
            dfs(i);
        }
    }
    ans[num--]='A'+x;
}
int main(){
    scanf("%d",&n);memset(t,0,sizeof(t));num=n;
    for(int i=0;i<=230;i++) fa[i]=i;
    for(int i=1;i<=n;i++){
        scanf("%s",op);
        int x1=op[0]-'A',x2=op[1]-'A';du[x1]++;du[x2]++;
        t[x1][x2]=1;t[x2][x1]=1;
        x1=get(x1);x2=get(x2);fa[x1]=x2;
    }
    int cnt=0;
    for(int i=0;i<=230;i++) if(du[i] && fa[i]==i) cnt++;
    if(cnt!=1){printf("No Solution\n");return 0;}
    int cnt1=0,head=-1;
    for(int i=0;i<=230;i++){
        if(du[i]%2){
            cnt1++;if(head==-1) head=i;
        }
    }
    if(cnt1 && cnt1!=2){printf("No Solution\n");return 0;}
    if(head==-1) for(int i=0;i<=230;i++) if(du[i]){head=i;break;}
    dfs(head);printf("%s",ans);return 0;
}