【Luogu1341】无序字母对（并查集联通，欧拉路模板）

problem

• 给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。
• 请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。
• 输出字典序最小的方案（n的规模局势所有字母随机组合的大小）

solution

——背景
欧拉路：能够从无向图中的一个节点出发走一条道路，每条边恰好经过一次，这样的道路称为欧拉道路。
判定和证明：当且仅当图中有两个奇点时存在欧拉道路（对于每个点，必须有进有出）。没有奇点时存在欧拉回路。（一个隐含的条件，前提是图必须联通。
——题解：
建图：把每个字母做为一个节点，字母对的相邻字母之间连一条边表示新序列(道路，经过这条)中他们必须相邻。
然后找欧拉路并打印解就是答案。欧拉路保证了每个字母对都会满足（每条边都会经过一次）。

codes

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 256;//ASCLL

//UnionFindSet判联通
int fa[maxn];
void init(int _n){for(int i = 1; i <= _n; i++)fa[i]=i;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x),y=find(y);fa[x]=y;}

//EulerRoad
int n, e[maxn][maxn], depth[maxn]; char ans[maxn];
void eular(int x){
    //cout<<(char)x;
    for(int i = 0; i < maxn; i++){
        if(e[x][i]){
            e[x][i] = e[i][x] = 0;//走过了就把边去掉
            eular(i);
        }
    }
    ans[n--] = x;//字典序最小
}

int main(){
    cin>>n;
    init(maxn-1);
    for(int i = 1; i <= n; i++){
        char t[10];  scanf("%s",t);
        e[t[0]][t[1]] = e[t[1]][t[0]] = 1;
        merge(t[0], t[1]);
        depth[t[0]]++, depth[t[1]]++;
    }
    //1.判联通
    int cc = 0;
    for(int i = 0; i < maxn; i++)//联通块个数
        if(fa[i]==i && depth[i])cc++;//dep保证是图上的节点
    if(cc != 1){ cout<<"No Solution"; return 0;}//不连通，不存在一笔画
    //2.有且仅两个奇点，欧拉道路
    int cnt = 0, star = 0;
    for(int i = 0; i < maxn; i++){
        if(depth[i]&1){
            cnt++;
            if(!star)star = i;//从奇点出发
        }
    }
    //3.没有奇点，欧拉回路
    if(cnt==0){
        for(int i = 0; i < maxn; i++){
            if(depth[i]){
                star = i; break;//随便找个图上的点出发
            }
        }
    }
    //4.奇怪的奇点，无解
    if(cnt && cnt!=2){ cout<<"No Solution"; return 0;}
    //5.输出路径
    eular(star);
    puts(ans);
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/81257645