algorithms

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

number-of-provinces.cpp (1059B)

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