Data structure - 《Leetcode》

178. Graph Valid Tree
629. Minimum Spanning Tree

Unordered_map
count(a) 查找a是否在unordered map中

Unordered_set

empty size .find() != .end
insert erase clear

Union Find
union find 模板

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    /**
     * @param n: An integer
     * @param m: An integer
     * @param operators: an array of point
     * @return: an integer array
     */
    int find(int x){
        if (x == father[x])
            return x;
        return father[x] = find(father[x]);
    }
    bool merge(int a, int b){
        if (father[a] == -1 || father[b] == -1)
            return false;
        int x = find(a);
        int y = find(b);
        if (x != y){
            father[x] = y;
            return true;
        }
        else
            return false;
    }
    bool inside(int x, int y, int n, int m){
        return (x >= 0 && y >= 0 && x < n && y < m);
    }
    vector<int> numIslands2(int n, int m, vector<Point> &operators) {
        // write your code here
        vector <int> row = {-1, 0, 1, 0};
        vector <int> col = {0, 1, 0, -1};
        int count = operators.size();
        int areaNum = 0;
        father.resize(m * n);
        for (int i = 0; i < m * n; i ++){
            father[i] = -1;
        }
        for (int i = 0; i < count; i++){
            int num = operators[i].x * m + operators[i].y;
            if (father[num] == -1){
                areaNum += 1;
                father[num] = num;
            }
            for (int j = 0; j < 4; j ++){
                int x = operators[i].x + row[j];
                int y = operators[i].y + col[j];
                if (inside(x, y, n, m)){
                    if (merge(x * m + y, num))
                        areaNum -= 1;
                }
            }
            res.push_back(areaNum);
        }
        return res;
    }
private:
    vector <int> father;
    vector <int> res;
};

Connecting Graph

class ConnectingGraph {
private:
vector <int> father;
public:
/*
* @param n: An integer
*/
ConnectingGraph(int n) {
   // do intialization if necessary
   father.resize(n + 1);
   for (int i = 0; i <= n; i ++){
       father[i] = i;
   }
}
int find(int x){
   if (father[x] == x){
       return x;
   }
   return father[x] = find(father[x]);
}
/*
* @param a: An integer
* @param b: An integer
* @return: nothing
*/
void connect(int a, int b) {
   // write your code here
   int x = find(a);
   int y = find(b);
   if (x != y){
       father[x] = y;
   }
}

/*
* @param a: An integer
* @param b: An integer
* @return: A boolean
*/
bool query(int a, int b) {
   // write your code here
   int x = find(a);
   int y = find(b);
   return x == y;
}
};

178. Graph Valid Tree

class Solution {
private:
    vector <int> father;
public:
    /**
     * @param n: An integer
     * @param edges: a list of undirected edges
     * @return: true if it's a valid tree, or false
     */

    int find(int a){
        if (father[a] == a){
            return a;
        }
        return father [a] = find(father[a]);
    } 
    bool merge(int a, int b){
        int x = find(a);
        int y = find(b);
        if (x != y){
            father[x] = y;
            return true;
        }
        return false;
    }
    bool validTree(int n, vector<vector<int>> &edges) {
        // write your code here
        father.resize(n);
        for (int i = 0; i < n; i ++){
            father[i] = i;
        }
        if (edges.size() != n - 1){
            return false;
        }
        for (int i = 0; i < n - 1; i ++){
            if (!merge(edges[i][0], edges[i][1])){
                return false;
            };
        }
        // int temp = find(0);
        // for (int i = 0; i < n; i ++){
        //     cout << father[i] << endl;
        //     if (find(i) != temp){
        //         return false;
        //     }
        // }
        return true;
    }
};

629. Minimum Spanning Tree

题意：
寻找最小的几条边使它能形成一棵树
comparator defination 在前面
@尹逸尘-Boston-sde 看了一下c++的文档，太复杂了啊，好像因为是接口设计的问题，sort的comparator既可以是一个pointer to function也可以是一个function object(aka functor)，而priority queue是接收一个class作为它的template parameter，这个class是用来产生一个function object，所以要overload the function call operator
@尹逸尘-Boston-sde 我感觉为什么有这个区别得原因，可能是因为priority_queue是一个class，而sort是一个function
所以前者接受一个class name作为它的template parameter，后者可以接受一个pointer to function或者object作为它的input argument
如果用sort（），写函数，< 升序
如果用PQ, > 前小后大，小顶堆

struct cmp是兼容C的class
class cmp 是C++的class
priority_queue 里面使用的cmp 是class -> struct cmp
sort 里面使用的cmp是function -> bool cmp.

/**
 * Definition for a Connection.
 * class Connection {
 * public:
 *   string city1, city2;
 *   int cost;
 *   Connection(string& city1, string& city2, int cost) {
 *       this->city1 = city1;
 *       this->city2 = city2;
 *       this->cost = cost;
 * }
 */

  bool cmp(const Connection& c1, const Connection& c2) {
      if (c1.cost != c2.cost)
          return c1.cost < c2.cost;

      if (c1.city1 != c2.city1)
          return c1.city1 < c2.city1;

      return c1.city2 < c2.city2;
  }

class Solution {
private:
    vector <int> father;
public:
    /**
    * @param connections given a list of connections include two cities and cost
    * @return a list of connections from results
    */

    int find(int a) {
        if (father[a] == a) {
            return a;
        }
        return father[a] = find(father[a]);
    }
    void merge(int a, int b) {
        int x = find(a);
        int y = find(b);
        if (x != y) {
            father[x] = y;
        }
    }
    vector<Connection> lowestCost(vector<Connection>& connections) {
        // Write your code here
        sort(connections.begin(), connections.end(), cmp);
        unordered_map <string, int> dict;
        vector<Connection> res;
        int count = 0;
        int countLines = 0;
        for (int i = 0; i < connections.size(); i++) {
            if (!dict.count(connections[i].city1)) {
                dict[connections[i].city1] = count++;
            }
            if (!dict.count(connections[i].city2)) {
                dict[connections[i].city2] = count++;
            }
        }
        father.resize(dict.size());
        for (int i = 0; i < dict.size(); i ++){
            father[i] = i;
        }
        for (int i = 0; i < connections.size(); i++) {
            if (countLines == dict.size() - 1) {
                return res;
            }
            int a = find(dict[connections[i].city1]);
            int b = find(dict[connections[i].city2]);
            if (a != b) {
                father[a] = b;
                countLines++;
                res.push_back(connections[i]);
            }
        }
        return vector<Connection>();
    }
};