Codeforces 939D - Love Rescue

传送门：http://codeforces.com/contest/939/problem/D

本题是一个数据结构问题——并查集（Disjoint Set）。

给出两个长度相同，且仅由小写字母组成的字符串S=s[1..n]、T=t[1..n]。已知一个无序对(u,v)可以完成任意次的以下转换操作：u→v，v→u。求将字符串S转换为T所需要的最少的无序对的数目，并打印出相应可行的方案下的所有无序对。

首先构造一张无向图G=<V,E>，表示S→T的状态转换图：结点集V={‘a’,’b’,’c’,...,’z’}；边集E={(s_i,t_i)|s_i≠t_i,i=1,2,...,n}。对于这张图的连通分量，构造一个边集最小的连通图——即无向图的生成树。可以采用简化的Kruskal算法求这棵生成树。

实际上，这是一个并查集的问题。通过并查集，对于每一个i，判断s_i、t_i是否在同一个集合中：若二者不在同一个集合中，则合并二者所在的集合。参考程序如下：

#include <stdio.h>

#include <stdbool.h>

#include <string.h>

#define MAX_V 26

#define MAX_N 100005

char s[MAX_N], t[MAX_N];

char uset[MAX_V], vset[MAX_V];

//Disjoint Set

int pa[MAX_V];

int rank[MAX_V];

void init(int n)

{

    memset(pa, , sizeof(pa));

    memset(rank, , sizeof(rank));

    for (int i = ; i < n; i++) {

        pa[i] = i;

        rank[i] = ;

    }

}

int find(int x)

{

    if (pa[x] == x) return x;

    else return pa[x] = find(pa[x]);

}

void unite(int x, int y)

{

    x = find(x);

    y = find(y);

    if (x == y) return;

    if (rank[x] < rank[y]) pa[x] = y;

    else {

        pa[y] = x;

        if (rank[x] == rank[y]) rank[x]++;

    }

}

bool same(int x, int y)

{

    return find(x) == find(y);

}

int main(void)

{

    int n;

    scanf("%d", &n);

    scanf("%s", s);

    scanf("%s", t);

    int cnt = ;

    init(MAX_V);

    for (int i = ; i < n; i++) {

        if (s[i] != t[i]) {

            int u = s[i] - 'a';

            int v = t[i] - 'a';

            if (!same(u, v)) {

                unite(u, v);

                uset[cnt] = u + 'a';

                vset[cnt] = v + 'a';

                cnt++;

            }

        }

    }

    printf("%d\n", cnt);

    for (int i = ; i < cnt; i++)

        printf("%c %c\n", uset[i], vset[i]);

    return ;

}

巴特西

Codeforces 939D - Love Rescue

最新文章

热门文章