990, satisfiability of equality equation

====

990, satisfiability of equality equation

====

Union_find

====

1. root單元是“字母” 不是給予eq.size

//eq.size是formula size

字母-“a"的差距

即可化為單元vec<int>

2. vec<string> eq

eq[0], [3]是字母單元

eq[1]是判斷

3. go through eq兩次

第一次先處理等於

如果eq[1]=='=' 則root[ep(0)] = root[eq(0)]

第二次處理不等於

如果eq[1]=='!'

但是先前的等於eq 讓單元root相等, 則flase

====

class Solution {

vector<int> root[26]

public equationPossible(vec<string>& equations) {

  

  for 0<26; root[i] = i

  for string eq:equations

    if eq[1] == '='

      root[ find(root, eq[3] -'a') ] = find(root, eq[0] -'a')

  for string eq:equations

    if eq[1] == '!'

      if find(root, eq[3] -'a') == find(root, eq[0] -'a') 

        return false

  return true

}

find(vec<int>root, int x){

  if root[i] == x

    return x

  return find(root, root[x])

}

1319, Number of operations to make network connected

====

1319, Number of operations to make network connected

====

Union find

====

1. 給予n台電腦, matrix of connection

所以matrix size至少要大約等於n-1

2. 給予root(n)紀錄單元root

如果有描述的link, root[y] = x

3. 如果有相同的root

(redundant (count++

====

class Solution:

vec<int> root(n)

public makeConnected(int n, vec<vec<int>>& con){

  int count=0, cable=con.size()

  if cable < n-1

    return -1

  else

    for i-n root[i] = I

    for i-n

      int x = getRoot(con[i][0])

      int y = getRoot(con[i][1])

      if x == y

        count++

      else

        root[y] = x

      return count

int getRoot(int i)

  if root[i] == I

    return i

  return getRoot(root[i])

947, Most stones remove with same row or column

====

947, Most stones remove with same row or column

====

1. 給予n個stones(雖然每個是座標)

因此給予一個root[n] 存放stone的root

//不要被座標混淆

2. 一樣初值n 假設每個stone單元都是獨立

3. for, for go through

每個stone, 與其他後順序的stone, 檢查座標

如果相同則root[j] = I

//是stone順序 //不要被座標混淆

最後for go through root

如果root[i] == i, (表示一個交集）加count

4. result為全部n 減去集合的count（=redundant

====

class Solution {

public removeStone(vec<vec<int>>& stone)

  int n= stone.size(), count= 0

  vec<int> root(n)

  for i-n root[i] = i

  for i; i<n; i++

    for j=i+1; j<n; j++

      if stone[i][0] == stone[j][0] ||

        stone[i][1] == stone[j][1]

          root[j] = i

  for i-n

    if root[i] == i count++

  return n-count

684, Redundant connection

====

684, Redundant connection

====

Union find

====

1. 使用一個list來紀錄每個單元的root

起始值都-1

2. for每個edge的點一，點二去找Root

如果（新的一輪edge(x, y)）x_root== y_root,

則是redundant, return edge

else, root[y]= x_root

====

class Solution {

public:

vec<int> root(2000, -1)

vec<int> findRedundant(vec<vec<int>>& M){

  

  for(int i=0; i<root.size(); i++) root[i] = i

  for(auto edge:M)

    int x = findRoot(edge[0])

    int y = findRoot(edge[1])

    if(x == y) return edge

    else

      root[y]= x

int findRoot(int i)

  if root[i] == i

    return i

  return findRoot(root[i])

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