785, is graph bipartite

785, is graph bipartite

====

coloring,

bipartition,

BFS

====

1. 同886, 給予一個vec<vec<int>>graph

限制不同屬的規則(dislike)

新增一個vec<int>color

0初值, 1,-1兩類

新增一個queue q處理每次的相關元素

2. while(!q.empty) 檢查所有元素規則

for cur, 當次元素

for nei, cur元素的graph規則

如果color[nei] != 0則skip

如果color[nei]=0, 未走訪 => 看color[nei] 與color[cur]

分兩類

如果分不了兩類, false

如果走完, q空都沒有failed, 則true

====

class Solution {

public:

  bool isBipartite(vec<vec<int>>&graph) {

    int n= graph.size()

    vec<int> color(n,0)

    queue<int> q

    for(int i=0, i<n, i++){

      if(color[i] != 0)

        continue

      color[i]=1

      for( q.push(i), !q.empty(), q.pop()) {

//這種寫法？！

        int cur=q.front()

        for( int nei: graph[cur]) {

          if(color[nei] == 0) {

            q.push(nei)

            color[nei] = color[cur]==1 ? -1 : 1

          }

          if(color[nei] == color[cur])

            return false

        }//graph[cur].size

      }//!q.empty()

    }//for n

    return true

  }

}

886, possible bipartition

886, possible bipartition

====

Coloring

Bipartition

====

1. 與union類似（？

給予一個vec<vec<int>> dislike的rule, 跟N個元素

->

新增一個vec<vec<int>> graph, 紀錄需要走訪的關係

//類似於union的input

新增一個color(N, 0)

0未走訪, 1,2兩類

新增一個queue處理當次graph元素的所有關係

//?

2. while(!q.empty) 檢查所有元素規則

for u, 當次元素

for v, u元素的graph規則

如果color[v] != 0則skip

如果color[v]=0, 未走訪 => 看color[u] 與color[v]

分兩類

如果分不了兩類, false

如果走完, q空都沒有failed, 則true

====

class Solution {

public:

  bool possibleBipartition(int N, vec<vec<int>&dislike) {

  vec<vec<int>>graph(N, vec<int>())

  queue<int> q

  vec<int> color(N, 0)

  for( i=0, i< dislike.size(), i++ ){

    u= graph[i][0] -1

    v= graph[i][1] -1

    graph[u].push_back(v)

    graph[v].push_back(u)

  }

  for( i=0, i<N, i++){

    if(color[i] != 0)

      continue

    q.push(i)

    color[i]=1 //起始

    while( !q.empty() ){

      u= q.front()

      q.pop()

      for( k=0, k<graph[u].size, k++ ){

        v= graph[u][k]

        if(color[v]==0){

          q.push(v)

          color[v] = color[u]==1 ? 2 : 1

        }

        if(color[v]==color[u])

          return false

      }//for graph[u].size

      

    }//while

  }//for N

  return true

  }

}

210, Course Schedule 2

210, Course Schedule 2

====

Topological sort

====

1. 給予一個node_number, 一個規則preReq vec<vec<>>

建立一個graph vec<vec<>>來紀錄topo //父子關係

2. 建立一個indegree

根據先後的規則 for紀錄每個node的深度

//聰明, 深度加在preReq的頭元素, 原則越多越深

//深度為0就是必須第一個走在前面的

3. 建立一個Queue nodes 存放走訪的點的順序,

//深度為0 加入queue

一個Int visit紀錄走過的點的數量, 判斷最終走過的點是不是全部點數量

//不是 則有cycle

4. 每當queue不為空

pop, push_back到ret

->

當次元素pop掉後, 去graph找接著的topo元素是哪些

->

這些topo元素, indegree -1

如果degree變0, 表示接著可以處理了, 加入queue

====

vec<int> findOrder(int numCourse, vector<pair<int, int>>& prerequest){

vec<vec<int>> graph(numCourse, vec<int>() )

vec<int> indegree(numCourse, 0)

queue<int> nodesQ

int visited=0

vec<int> ret

for( auto eq: prerequest ){

  graph[eq.second].push_back( eq.first )

  indegree[eq.first]++

}

for( int n, n<numCourse, n++)

  if(indegree[n] == 0)

    nodeQ.push(n)

while(!nodeQ.empty()){

  visited++

  int nid = nodeQ.front()

  nodeQ.pop()

  ret.push_back(nid)

  for( auto topo:graph[nid] ){

    indegree[topo]--

    if(indegree[topo]==0)

      nodeQ.push(topo)

  }

}//while empty

return visited==numCourse ? ret : vec<int>()

}

207, Course schedule

207, Course schedule

====

Topological sort

Coloring

====

1. 給予一個n node number

一個vec<pair<int,int>>prerequest規則

2. prerequest表明<i,j>(有向圖)

如果要access i, 必須先有j

如果規則互斥(產生cycle) 則false

可能有很多方式

可用DFS 可用BFS 可用coloring

3. Coloring比較單純

生成一個map<int, vec<int>> adj來填入規則 //hashMap

->

adj[1].push_back(0)

生成一個vec<int> visited(n,0)來紀錄

如果走的過程中有碰到任何已經拜訪過的

則有cycle, false

否則true

====

class Solution{

public:

bool isCycle(vec<int>visited, vec<vec<int>>adj, int id){

  if visited[id] == 1 return true

  if visited[id] == 0{

    visited[id]=1

    for auto edge:adj[id]

    if isCycle(visited, adj, edge) return true

  }

  visited[id]=2 //?

  return false

}

bool canFinished(int n, vec<vec<int>>& pre){

  map<int, vec<int>> adj

  for auto edge: pre

    adj[edge[1]].push_back(edge[0])

  vec<int> visited(n, 0)

  for auto prule: adj{

    if(isCycle(visited, adj, prule.first)) return false

  }//

return true

}

};

1091, Shortest path in binary matrix

1091, Shortest path in binary matrix

====

BFS,

Shortest path,

Path existed

====

1. 題目給予vec<vec<int>>matrix

從左上 欲走到右下

路徑上只能是0 可以走八個方向

2. 一個queue< pair<int,int>>做BFS

一個vec<vec<bool>> visited記錄走過

3. 起點是左上

找它的鄰近加入queue

紀錄每次queue.size

而後每次找鄰近 且 matrix[][]==0 加入queue

4. 每次round++

當有座標碰到右下

return round(左上）

====

class Solution {

public:

int shortestPathBinaryMatrix(.vec<vec<int>>& grid ){

  int m= grid.size(), n= grid[0].size()

  if( grid[0][0]!=0 || grid[m-1][n-1]!=0 ) return -1

  queue< pair<int,int>> pq

  pq.push({1,0}), pq.push({0,1}), pq.push({1,1})

  vec<vec<bool>> visited=(m, vec<bool>(n, false))

  int res=1 //第一輪

  while(!pq.empty()){

    int qSize= pq.size()

    for(int t-qSize){

      auto qFront= pq.front()

      pq.pop()

      int x= qFront.first

      int y= qFront.second

      

      if(x==m-1 && y==n-1) return res+1 //第n輪加上右下+1

      if(x>=0 && y>=0 && x<m && y<n && !visited[x][y] && grid[x][y]==0){

        visited[x][y]=true

        pq.push({x-1,y-1}), pq.push({x-1,y}), pq.push({x-1,y+1})

        pq.push({x,y-1}), pq.push({x,y+1})

        pq.push({x+1,y-1}), pq.push({x+1,y}), pq.push({x+1,y+1})

      }//if

    }//for qSize

    res++

  }//while q.empty

  return -1

}

};

994, rotting oranges

====

994, rotting oranges

====

BFS,

Shortest path,

Path existed

====

1. 給予一個箱子

'0'代表空

'1'代表好的

'2'代表爛的橘子

每分鐘爛的會向四個方向腐爛

求最大（久）箱子內還有好的

2. 起點是爛的->爛的(2) 座標/pair加入queue

隨後加入找好的(1)

但是要把它變爛(2)才 座標/pair加入queue

3. 多一個int fresh紀錄剩餘的好的

每次BFS加入記得扣掉

多一個int res紀錄第幾輪

return res

//剛開始的BFS還沒開始感染

//所以放在while裡面即可

4. 四個方向化成一個vector

vec<int> for={-1, 0, 1, 0, -1}

//只要1234, 2345 pair就好

====

class Solution{

public:

int orangesRotten( vec<vec<int>>& grid ){

  int m= grid.size(), n= grid[0].size()

  int fresh=0

  queue< pair<int,int>> q

  for i-m

    for j-n

      if grid[i][j] == 2

        q.push(<i-1,j>), q.push(<i+1,j>), q.push(<i,j-1>), q.push(<i,j+1>);

      if grid[i][j] == 1

        fresh++

  vec<vec<bool>> visited(m, vec<bool>(n, flase))

  int res=-1

  while( !q.empty() ){

    int qSize= q.size()

    while(qSize--){

      auto fq= q.front()

      q.pop()

      int x= fq.first

      int y= fq.second

      if(x>=0 && y>=0 && x<m && y<n && !visited[x][y] && grid[x][y]==1){

        visited[x][y]=true

        grid[x][y]=2

        q.push(<x-1,y>), q.push(<x+1,y>), q.push(<x,y-1>), q.push(<x,y+1>);

      }//if

    }//q.size

    res++

  }//q.empty

if(res==-1) return 0

if(fresh>0) return -1 //有橘子永遠不爛 莫急

}

};

1162, As far from land as possible

====

1162, As far from land as possible

====

BFS,

Shortest path

Path existed

====

1. 目標是water, '0'

能有與

起點land, '1'能有的最長距離

2. 

定義一個queue<pair<int,int>>存放座標

BFS第一輪找的是起點->從'1'開始上下左右加第一輪BFS

3. 當queue不為空

front && pop座標

如果符合條件 //!visited && 是目標'0'

=>

visited true/ update cost/ 加入上下左右BFS

4. 當最遠的座標找到 會結束

=>

最遠的座標 在上一輪會將上下左右加入queue

=>

新的一輪 for step++

=>

都不符合條件 pop

一直都沒有符合條件的座標 所以都沒有加入queue

=>

while queue空了 跳出

=>

這次的step無作用

step-1才是預期

====

class Solution{

public:

int maxDistance( vec<vec<int>>& matrix ){

  int m= matrix.size(), n= matrix[0].size()

  vec<vec<bool>> visited= (m, vec<bool>(n, false))

  queue<pair<int,int>> pq

  for i-m

    for j-n

      if matrix(i,j) == 1

        pq.push(i-1,j)

        pq.push(i+1,j)

        pq.push(i,j-1)

        pq.push(i,j+1)

  int step=0

  while(!pq.empty()){

    step++

    int size=pq.size()

    for t-size{

    int x= pq.front().first

    int y= pq.front().second

    pq.pop()

    if( x>=0 && y>=0 && x<m && y<n && matrix(x,y)==0 && !visited(x,y) ){

      visited(x,y) = true

      pq.push(x-1,y)

      pq.push(x+1,y)

      pq.push(x,y-1)

      pq.push(x,y+1)

    }//if

    }//for

  }//while

  return step==1? -1: step-1

}

};

542, 01_matrix

====

542, 01_matrix

====

BFS,

Shortest path

Path existed

====

1. 題目希望將給予的matrix

化成

每個單元離它最近的'0'的距離

2. BFS用的是queue, 因為用了座標

所以用queue< pair<int,int> >來紀錄加入queue的座標

3. 從(0,0)開始做BFS

當queue不為空的時候

-> pop單元

-> 針對pop的動作處理BFS //加入新的單元

//新增step or cost

4. Visited是必須的

產生一個vec<vec<bool>>visited來紀錄已經處理過的單元

以免單元間產生無窮迴圈

->

當沒有visited

且

符合題目條件

則處理

BFS //push

====

class Solution{

public:

vec<vec<int>> updateMatrix( vec<vec<int>>&matrix ){

  int m= matrix.size()

  int n= matrix[0].size()

  queue<pair<int,int>> pq

  for i-m

    for j-n

      if(matrix(i,j) == 0){

      //先從'0'開始 因為第一次與零的距離是“0”

      //之後逐漸加一

        pq.push({i-1, j});

        pq.push({i+1, j});

        pq.push({i, j-1});

        pq.push({i,j-1});

        //上下左右加入queue //所有第一層的node

      }

  int step=0

  vec<vec<bool>> visited(m, vec<bool>(n, false) )

  while( !pq.empty() ){

  step++

  int size= pq.size() //紀錄當前的queue size來控制當次需要做多少次

  for(i=0; i<size; i++){

    auto Front= pq.front()

    int x=Front.first

    int y=Front.second

    pq.pop()

    if(x>=0&& y>=0&& x<m&& y<n&& !visited(x,y)&& matrix(x,y)==1){

      //開始找‘1’,因為開始要填1到0的距離

      visited(x,y)=true

      matrix(x,y)=step

      //因為拜訪過了 且當前的距離已經填入

      pq.push({x-1, j});

      pq.push({x+1, j});

      pq.push({i, y-1});

      pq.push({i,y-1});

      //第n次層的上下左右 加入queue

    }//if

  }//for

  }//while

}

};

802, Find eventual safe states

====

802, Find eventual safe states

====

DFS,

cycle find

有向/無向圖找cycle不一樣

有向需要三個顏色(還沒看過/ 還在看/ 已經看完

無向需要兩個顏色(visited/ un-visited

過程中有碰到訪問過/看過的node

就是有cycle

====

a)

1. 題目給予一個graph

定義一個int dp(n, 0)初值

0, 還沒看過

-1,還在看

1,已經看完

2. DFS一進去

先將dp[i]=-1 //還在看

然後針對graph[i][]一一DFS檢查

如果有false則return false

3. 如果graph[i][]跑完 都沒看到cycle 

//如果沒有看到dp==-1, i.e還在看

則dp[i]=1, i.e已經看完

return true

else

return dp[i]==1

4. main一個for跑DFS

如果false,就不加入結果

否則是安全的,加入

====

class Solution{

public:

bool DFS( vec<vec<int>>&graph, vec<int>&dp, int i){

  if ( dp[i] ) //-1 ->false, 1 ->true

    return dp[i]==1

  dp[i]=-1

  for auto t:graph[i].begin; t!=graph[i].end; t++

    if ( !DFS( graph, dp, *t ) )

      return false

  dp[i]=1

  return true;

}

vec<int> eventualSafe( vec<vec<int>>&graph ){

  int n=graph.size()

  vec<int> res

  vec<int> dp(n, 0)

  for i-n

    if( DFS( graph, dp, i )

      res.push_back(i)

  return res

}

}

733, Flood Fill

====

733, Flood Fill

====

DFS,

from each un-visited node/island problems

====

1. 題目給予一個vec<vec<int>>M

一個起始的座標

以及變更的新數值

2. 定義一個vec<vec<bool>>visited

DFS( M, visited, i, j, m, n, new )走過上下左右的同值/同於起始 的所有node

====

class Solution{

void DFS( vec<vec<int>>& matrix, vec<vec<bool>>&visited, int i, int j, int m, int n, int old, int new){

  if( i<0 || j<0 || i>=m || j>=n || matrix(i,j)!=old || visited(i,j) ) return;

  visited(i,j)= true;

  matrix(i,j)= new;

  DFS( matrix, visited, i-1, j, m, n, matrix(i,j), new)

  DFS i+1

  DFS j-1

  DFS j+1

}

vec<vec<int>> FloodFill( vec<vec<int>>& matrix, int x, int y, int newColor ){

  int m= matirx.size(), n= matrix[0].size()

  vec<vec<bool>> visited= (m, false)

  if matrix(x,y)!=newColor

    DFS( matrix, visited, x, y, matrix(x,y), newColor)

  return matrix

}

841, Keys and rooms

====

841, Keys and rooms

====

DFS,

for each unvisited node/island problems

====

1. 題目給予固定長度n的房間 以及房間內含的鑰匙

題目定義第一間是沒有鎖的=>DFS開始的地方

生成一個n的visited

2. DFS走過所有的鑰匙

最終for檢查visited

如果還有房間un-visited則false

====

class Solution{

public:

void DFS( vec<vec<int>>&rooms, vec<bool>&visited, int node){

  visited[node]=true

  for auto k:rooms[node]

    if( !visited[k] )

      DFS( rooms, visited, k )

}

bool VisitedRoom( vec<vec<int>>& rooms ){

  int n=rooms.size()

  vec<bool> visited(n, false)

  DFS( rooms, visited, 0 )

  int i=0

  for i-n

    if !visited[i] return false

  return true

}  

1254, Number of closed islands

====

1254, Number of closed islands

====

DFS from each unvisited node/island problem

====

a)

----

1. 題目給予一個vec<vec<char>>的網絡（grid

生成一個vec<vec<bool>>的visited

來表示這個node是不是檢查過了

//因為DFS有上下左右 可能先前被查過了

2. （看題目）定義DFS的行為:

DFS( grid, visited, i, j, m, n )

->

如果超界, 如果是'0', 如果造訪過了 return

else, 

visited改成true

這個node的上下左右去做DFS

3. 回到main（看題目）定義main的行為:

for for grid

如果是'1', 如果還沒造訪過 則

DFS( grid, visited, i, j, m, n )

count++

//因為DFS會做完, 能連到的都連完了, 才跳出

//就找到一個island

//如果for又找到 應該又是全新的island 故重新算重新加

====

class Solution{

void DFS( vec<vec<int>>&grid, vec<vec<bool>>&visited, int i, j, m, n){

  if i<0 || j<0 || i>=m || j>=n || visited(i,j) || grid(i,j)!='1'

    return

  visited(i,j)=true

  DFS( grid, visited, i-1, j, m, n)

  DFS(i+1

  DFS(j-1

  DFS(j+1

}

public:

int closedIsland (vec<vec<int>>&grid){

  int m=grid.size()

  int n=grid[0].size()

  vec<vec<bool>> visited(m, vec<bool>(n, false))

  int count=0

  for i-m

    for j-n

      if( grid [i][j] == '1' && !visited[i][j] ){

        DFS( grid, visited, i, j, m, n)

        count++

      }

  return count

}

};

1376, Time needed to inform all employees

====

1376, Time needed to inform all employees

====

DFS,

Time taken to reach all nodes, or share info to all graph nodes

====

1. 題目給予一個vec<int> manager

=>

生成一份vec<vec<int>> children

or

map<int, vec<int>> children

children用意在紀錄node擁有的child

(可視為hash map

2. 因為children會紀錄所mana<->child關係

所以從root(題目給的headID) 開始DFS

會走過所有node

3. 題目給予一個 vec<int>informTime

定義一個resource 為最終total結果

每次DFS,

一個current為加上目前informTime[i]的時間

每次DFS 比較max(resource, current)

最終return resource

====

class Solution{

int DFS( vec<vec<int>>&child, int node, vec<int>&time){

if child[node].size == 0

  return 0

  //本次node沒有children, time沒有增加, return

int ans= time[node]

int tempMax= 0

for(auto c: child[node]){

  tempMax = max( tempMax, DFS( child, c, informTime)

//如果child有多個 會停在for裡面

//當有找到更大的結果 會丟給tempMax

//當次還沒return就不會被清零

//清零用意只是紀錄當次node子集裡的最大

}

return ans+tempMax

//結果等於 當前的time[node] 

//加上

//子集裡面最大的time

}

public:

int numOfMinute( int n, int headID, vec<int>& manager, vec<int>& informTime){

vec<vec<int>> children(n)

for int i=0; i<n; i++

  if manager[i] != -1

    children[ manager[i] ].push_back(i)

return DFS( children, headID, informTime )

}

130, Surrounded regions

130, Surrounded regions

====

DFS boundary

====

1. 題目是說被1包圍的0 可以被翻牌

=>

沒有碰到邊界的0 可以被翻牌

（有連結到）碰到邊界的0無法被翻牌

2. 從邊界開始找有沒有0

當找到邊界為0, 對它的做DFS(上下左右)

找到的0, 先把它變更符號e.g.#

3. for, for go through

剩下的0是可以翻成1的

剩下的#是不能翻的 翻回0

====

class Solution{

public:

  void surroundRegion(vec<vec<char>>&board){

    int m=board.size(), n=board[0].size()

    for int i=0; i<m; i++

      if board[i][0] == 'o'

        DFS(board, i, 0, m, n)

      if board[i][n-1] == 'o'

        DFS(board, i, n-1, m, n)

    for int j=0; j<n; j++

      if board[0][j] == 'o'

        DFS(board, 0, j, m, n)

      if board[m-1] == 'o'

        DFS(board, m-1, j, m, n)

    for i-n

      for j-n

        if board[i][j] == 'o'

          board[i][j] = 'x'

        if board[i][j] == '#'

          board[i][j] = 'o'

}

void DFS(vec<vec<char>>board, int i, j, m, n){

  if i<0 || j<0 || i>=m || j>=n || board(i,j)!='o'

    return

  board(i,j) = '#'

  DFS(i-1, j, m, n)

  DFS(i+1, j, m, n)

  DFS(i, j-1, m, n)

  DFS(I, j+1, m, n

}

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