MST

solution

在写这一篇的时候，这题非常出名，因为16年秋首批爆出的video第三题都是这道。做出来的就能拿到video，价值108k+18k美刀至少，比摸金校尉三人合体都多，做不出来也能免费去西雅图来一圈儿，吃喝减半住宿全免，但群面通过率远低于video，所以为了生存这道题必须跑出来。

题目内容是这样的，给十几个城市供电，连接不同城市的花费不同，让花费最小同时连到所有的边。给出一系列connection类，里面是edge两端的城市名和它们之间的一个cost，找出要你挑一些边，把所有城市连接起来并且总花费最小。不能有环，最后所以城市要连成一个连通块。

不能的话输出空表，最后还要按城市名字排序输出，按照node1来排序,如果一样的话再排node2。

输入:

{"Acity","Bcity",1}

("Acity","Ccity",2}

("Bcity","Ccity",3}

输出：

("Acity","Bcity",1}

("Acity","Ccity",2}

补充一句，test case一共有6个。

思路会有很多，我的想法是Kruskal+Union Find，将输入的一群connection类（其实就是边）按照cost从小到大排序(Kruskal算法)，然后遍历。挑出一个connection之后，看一下edge两头的城市属于哪一个团伙(Union Find)。如果落单了就加入，不同团伙就合并，都是落单了就抱团。最后有两个要求，1.如果MST不存在，那么输出一个空表（应该不是null）。这个可以用union find思想，最后查有几个union，如果大家都是自己人，那么就正常输出，如果大家是1，有零星2了，那就空表了。2.输出要按照城市的名字排序，这个不难，就正常排序就行。

https://segmentfault.com/a/1190000007064752

youtube教程

code

class unionfind {
public:
    map<int, int> hash;
    map<string, int> wordmap;
    int index;

    unionfind()
    {
        this->index = 1;
    }

    void add(string key)
    {
        if(wordmap.find(key) == wordmap.end())
        {
            wordmap[key] = index++;
            hash[wordmap[key]] = wordmap[key];
        }
        else
        {
            hash[wordmap[key]] = wordmap[key];
        }

    }

    int find(string keystring)
    {
        int key = wordmap[keystring];
        while(key != hash[key])
        {
            key = hash[key];
        }
        return key;
    }

    int compress_find(string keystring)
    {
        int key = wordmap[keystring];
        int boss = find(keystring);
        while(key != boss)
        {
            int next = hash[key];
            hash[key] = boss;
            key = next;
        }
        return boss;
    }

    bool bossunion(string a, string b)
    {
        int fa = compress_find(a);
        int fb = compress_find(b);

        if(fa != fb)
        {
            hash[fa] = fb;
            return true;
        }

        return false;
    }
};

class connection {
public:
    string a;
    string b;
    int cost;
    connection(string a, string b, int cost)
    {
        this->a = a;
        this->b = b;
        this->cost = cost;
    }
};

typedef bool (*costcomp)(connection a, connection b);
bool costCompare(connection a, connection b)
{
    return a.cost > b.cost;
}

typedef bool (*namecomp)(connection a, connection b);
bool nameCompare(connection a, connection b)
{
    if(a.a != b.a)
    {
        return a.a > b.a;
    }
    else
    {
        return a.b > b.b;
    }
}

vector<connection> mst(vector<connection>& vec)
{
    vector<connection> ret;
    if(vec.empty())
    {
        return ret;
    }

    priority_queue<connection, vector<connection>, costcomp> heap(costCompare);
    priority_queue<connection, vector<connection>, namecomp> heap2(nameCompare);
    unionfind uf;

    for(int i = 0; i<vec.size(); i++)
    {
        heap.push(vec[i]);
        uf.add(vec[i].a);
        uf.add(vec[i].b);
    }

    while(!heap.empty())
    {
        connection cur = heap.top();
        heap.pop();

        int indexa = uf.compress_find(cur.a);
        int indexb = uf.compress_find(cur.b);
        if(indexa != indexb)
        {
            heap2.push(cur);
            uf.bossunion(cur.a, cur.b);
        }
    }

    while(!heap2.empty())
    {
        connection cur = heap2.top();
        heap2.pop();
        ret.push_back(cur);
    }

    return ret;
}

int main(int argc, const char * argv[])
{
    // insert code here...
    std::cout << "Hello, World!\n";

    vector<connection> vec;
    vec.push_back(connection("a", "b", 4));
    vec.push_back(connection("a", "f", 2));
    vec.push_back(connection("f", "b", 5));
    vec.push_back(connection("c", "b", 6));
    vec.push_back(connection("c", "f", 1));
    vec.push_back(connection("f", "e", 4));
    vec.push_back(connection("d", "e", 2));
    vec.push_back(connection("d", "c", 3));

    for(connection a : mst(vec))
    {
        cout<<a.a<<" "<<a.b<<" "<<a.cost<<endl;
    }

    return 0;
}