547, Number of provinces

====

547, Number of provinces/省

====

Union find

====

1. 使用一個list: Root紀錄每個單元的 _root

2. 預設一個group為n

(即一開始每個單元都是獨立的 可視為n的獨立集合

3. for gothrough每個link/M(I,j)

如果

M(I,j)== 1, i_root!= j_root, 則把Root[j]= i_root, group--

(找到一個單元是可以被包含的

====

class Solution:

public findProvince(vec<vec<int>>M)

  int n=M.size(), group=n

  vec<int> Root

  for i-n: Root[i]=i

  for i-n:

    for j-n:

      if M[i][j]==1

        int p1 = getRoot(Root, i)

        int p2 = getRoot(Root, j)

        if (p1 != p2)

          group--

          Root[p2] = p1

int getRoot(vec<int>&Root, int i)

  if(Root[i]!=i)

    Root[i] = Root[ Root[i] ]

    i=Root[i]

  return i