YEZAELP

LeetCode: Redundant Connection

Dec 27th, 2021 (edited)
73
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int parent[1010];
  4.  
  5.     int root(int u){
  6.         if(parent[u] == u) return u;
  7.         return parent[u] = root(parent[u]);
  8.     }
  9.  
  10.     void mrg(int u, int v){
  11.         u = root(u);
  12.         v = root(v);
  13.         parent[v] = u;
  14.     }
  15.  
  16.     vector<int> findRedundantConnection(vector<vector<int>>& edges){
  17.        
  18.         for(int u=1;u<=1000;u++)
  19.             parent[u] = u;
  20.        
  21.         int a = -1, b = -1;
  22.         for(auto e: edges){
  23.             int u = e[0];
  24.             int v = e[1];
  25.             if(root(u) == root(v))
  26.                 a = u, b = v;
  27.             mrg(u, v);
  28.         }
  29.         return {a, b};
  30.     }
  31. };
RAW Paste Data Copied