乐视编程题_困兽之斗

描述

经过深思熟虑之后，小贱君打算去M国闯一闯，那是一个古老的东方国度，传说有很多高阶魔法师，他想成为一名伟大的魔法师，将来征服星辰大海。

经过千辛万苦，小贱君终于来到了M国，不幸的是刚进城门小贱君就被M国的守城士兵困在了一种叫做“困兽之斗”的阵法之中。

士兵对小贱君说：“看到漂浮在你身边的宝石了吗？彩虹连接的两颗宝石可以任意交换位置，你需要通过一系列交换后使得宝石组成的字符串的字典序最小。若不能破阵，那还是请回吧！”

小贱君观察了一下周围的宝石，只见每颗宝石上标有一个小写字母，而且有一些宝石上通过彩虹与其他宝石相连。

琢磨了半天，他终于搞懂了这个阵法的意思：

若宝石系列为：dcba

其中有两道彩虹，分别是(0,1),(1,2),代表第一个位置上的宝石可以和第二个位置上的宝石互换，第二个位置上的宝石可以和第三个位置上的宝石互换，最终可以得到字典序最小的宝石系列：bcda。

作为小贱君的死党，你有什么方法帮助他破阵吗？

输入描述:

输入包含多组测试数据。
对于每组测试数据：
字符串s — 代表宝石序列
n — 代表有n条彩虹
接下来n行，每行两个数ai,bi — 表示ai和bi由一条彩虹相连。
保证：
1<=s的长度<=10000
1<=n<=10000
且输入数据均合法。

输出描述:

对于每组数据，输出一个字符串

输入例子:

dcba
2
0 1
1 2
hellonowcoder
4
0 1
1 4
2 5
2 3

输出例子:

bcda
ehllonowcoder

思路

并查集，然后对同一集合的元素排序，赋值给对应的位置

代码

//乐视2017实习生在线编程，编程题：困兽之斗
//并查集
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <unordered_map>
#include <algorithm>

//using namespace std;

#define MAX 10001   //自己设置最大值

// father[x]表示x的父节点
int father[MAX];
// rank[x]表示x的秩
int rank[MAX];

// 初始化
void Make_Set(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        father[i] = i;
        rank[i] = 0;
    }
}

// 查找
int Find_Set(int x)
{
    if (x != father[x])
        return Find_Set(father[x]);
    return x;
}

// 合并
void Union(int x, int y)
{
    x = Find_Set(x);
    y = Find_Set(y);
    if (x == y)  // x,y在同一个集合
        return;
    if (rank[x] > rank[y])
        father[y] = x;
    else if (rank[x] < rank[y])
        father[x] = y;
    else
    {
        rank[y]++;
        father[x] = y;
    }
}

int N, M;
int main()
{
    std::string str;
    int a, b;
    while (std::cin >> str)
    {
        //first为顶层的father节点，msets中记录该father节点下的全部节点
        std::unordered_map<int, std::vector<char>> msets;
        //first为顶层的father节点,vector中记录相应节点的位置
        std::unordered_map<int, std::vector<int>> midxs;
        N = str.length();
        for (int i = 1; i <= N; ++i)
            Make_Set(i);
        std::cin >> M;
        while (M--)
        {
            std::cin >> a >> b;
            Union(a+1, b+1);
        }
        int cnt = -1;
        for (int i = 1; i <= N; ++i)
        {
            int idx = Find_Set(i);
            msets[idx].push_back(str[i-1]);
            midxs[idx].push_back(i-1);
        }

        for (auto it = msets.begin(); it != msets.end(); ++it)
        {
            std::vector<char> char_vec = it->second;
            std::vector<int> idx = midxs[it->first];
            //字符序，排序
            std::sort(char_vec.begin(), char_vec.end());
            //排序后赋值
            for (int i = 0; i < char_vec.size();i++)
            {
                str[idx[i]] = char_vec[i];
            }
        }
        std::cout << str << std::endl;
    }
    return 0;
}