algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

number-of-provinces-v2.cpp (1305B)

      1 class Node {
      2     public:
      3         Node* parent = nullptr;
      4         int size = 1;
      5 };
      6 
      7 Node* find(Node& a){
      8     if(a.parent == nullptr) {
      9         return &a;
     10     }
     11     auto found = find(*a.parent);
     12     a.parent = found;
     13     return found;
     14 }
     15 
     16 void union_nodes(Node& a, Node& b) {
     17     auto p_a = find(a);
     18     auto p_b = find(b);
     19     if(p_a != p_b) {
     20         if(p_a->size > p_b->size) {
     21             p_b->parent = p_a;
     22             p_a->size += p_b->size;
     23         } else {
     24             p_a->parent = p_b;
     25             p_b->size += p_a->size;         
     26         }
     27     }
     28 }
     29 
     30 class Solution {
     31 public:
     32     int findCircleNum(vector<vector<int>>& isConnected) {
     33 
     34         unordered_map<int, Node*> provinces {};
     35 
     36         for(int i = 0; i < isConnected.size(); ++i) {
     37             Node* node = new Node();
     38             provinces[i] = node;
     39         }
     40 
     41         for(auto pair: provinces) {
     42             vector<int>& adj = isConnected[pair.first];
     43             for(int i = 0; i < adj.size(); ++i) {
     44                 if(adj[i]) {
     45                     union_nodes(*provinces[i], *pair.second);
     46                 }
     47             }
     48         }
     49 
     50         unordered_set<Node*> reps {};
     51 
     52         for(auto pair: provinces) {
     53             auto rep = find(*pair.second);
     54             reps.insert(rep);
     55         }
     56         
     57         return reps.size();
     58     }
     59 };