【Luogu1341】无序字母对(并查集联通,欧拉路模板)

            

problem

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

solution

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

codes

#include
#include
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;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像