[LeetCode 解題筆記] Number of Provinces

原問題網址: 547. Number of Provinces

問題描述

n 個城市,有些城市相連、有些城市沒有。如果城市 a 直接與城市 b 相連,且城市 b 直接與城市 c 相連,則城市 a 間接與城市 c 相連。

一個省(province)為一組直接或間接相連的城市。

題目給定一個 n x n matrix isConnected ,如果 isConnected[i][j] = 1 ,代表第 i 個城市跟第 j 個城市直接相連。( 0 代表沒有相連)

return 省的總數量。

解題思路

這一題可以用演算法或資料結構課程中會提到的 Disjoint-set forests 解決。(詳情可以參考演算法聖經教科書 CLRS)

以下為用 C 語言實作的程式碼:

struct DisjointSet {
  struct DisjointSet *parent;
  int key;
  int rank;
};

struct DisjointSet *make_set(int key) {
  struct DisjointSet *root = malloc(sizeof(struct DisjointSet));
  root->parent = root;
  root->key = key;
  root->rank = 0;
  return root;
}

// path compression
struct DisjointSet *find_set(struct DisjointSet *set) {
  if (set->parent != set) {
    set->parent = find_set(set->parent);
  }
  return set->parent;
}

//union-by-rank + path compression
void union_set(struct DisjointSet *a, struct DisjointSet *b) {
  struct DisjointSet *root_a = find_set(a);
  struct DisjointSet *root_b = find_set(b);
  if (root_a->rank > root_b->rank) {
    root_b->parent = root_a;
  } else {
    root_a->parent = root_b;
    if (root_a->rank == root_b->rank) {
      root_b->rank += 1;
    }
  }
}

int findCircleNum(int** isConnected, int isConnectedSize, int* isConnectedColSize){
  struct DisjointSet **handles = malloc(sizeof(struct DisjointSet *) * isConnectedSize);
  for (int i = 0; i < isConnectedSize; i++) {
    handles[i] = make_set(i);
  }
  for (int i = 0; i < isConnectedSize; i++) {
    for (int j = 0; j < *isConnectedColSize; j++) {
      if (isConnected[i][j] == 1) {
        union_set(handles[i], handles[j]);    
      }
    }
  }
  
  int provinces_count = 0;
  for (int i = 0; i < isConnectedSize; i++) {
    if (handles[i]->parent == handles[i]) {
      provinces_count++;    
    }
  }
    
  //free memory
  for (int i = 0; i < isConnectedSize; i++) {
    free(handles[i]);
  }
  free(handles);
  return provinces_count;
}
Show Comments