leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

number-of-provinces.dart (1665B)

      1 //Given a list of lists showing a nodes undirected connections
      2 //return how many seperate groups of nodes there are.
      3 
      4 //Ex Input: [1,1,0], [1,1,0] [0,0,1]
      5 //The above input is three nodes the first two are
      6 //connected to each other and the final node is not connected
      7 //to any nodes.
      8 
      9 //To solve this I first converted the input list to an adjacency list
     10 //to simplify the process of doing bfs. Then from there I iterated through the list
     11 //and for each unvisited node I found added one to the total number of groups and then ran
     12 //BFS on it adding all connected nodes to visited.
     13 
     14 //Time: 299ms Beats: 71.43%
     15 //Memory: 150.7MB Beats: 28.57%
     16 
     17 class Solution {
     18   int findCircleNum(List<List<int>> isConnected) {
     19       Map<int, List<int>> adj_list = {};
     20       for(int i = 0 ; i < isConnected.length ; ++i){
     21               List<int> current_adj = [];
     22           for(int x = 0 ; x < isConnected[i].length ; ++x){
     23               if(isConnected[i][x] == 1){
     24                 current_adj.add(x);
     25               }
     26           }
     27           adj_list[i] = current_adj;
     28       }
     29       Set<int> explored = {};
     30       int provinces = 0;
     31       for(var vert in adj_list.entries){
     32         if(explored.contains(vert.key)){
     33           continue;
     34         }
     35         provinces += 1;
     36         searchConnected(explored, adj_list, vert.key);
     37       }
     38       return provinces;
     39   }
     40   void searchConnected(Set<int> searched, Map<int, List<int>> adj_list, int current){
     41     if(searched.contains(current)){
     42       return;
     43     }
     44     searched.add(current);
     45     List<int> current_list = (adj_list[current] ?? []);
     46     for(int vertex in current_list){
     47       searchConnected(searched, adj_list, vertex);
     48     }
     49   }
     50 }