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])