redundant-connection.cpp (2068B)
1 class Node { 2 public: 3 Node* parent = nullptr; 4 int identifier; 5 int size = 1; 6 }; 7 8 Node* find(Node* a) { 9 if(a->parent == nullptr) { 10 return a; 11 } 12 else { 13 auto* rep = find(a->parent); 14 a->parent = rep; 15 return rep; 16 } 17 } 18 19 // return true if union must be done, false if both have same rep. 20 bool union_sets(Node* n1,Node* n2) { 21 auto p_1 = find(n1); 22 auto p_2 = find(n2); 23 24 if(p_1->identifier == p_2->identifier) { 25 return false; 26 } 27 28 if(p_2->size < p_1->size) { 29 p_2->parent = p_1; 30 p_1->size += p_2->size; 31 } else { 32 p_1->parent = p_2; 33 p_2->size += p_1->size; 34 } 35 return true; 36 } 37 38 class Solution { 39 public: 40 vector<int> findRedundantConnection(vector<vector<int>>& edges) { 41 // idea: 42 // - mst where edges are weighted based on position in edges list 43 // - union find where we join on edges in order of inputs 44 // - iff union(a,b) is non-changing, put edge a,b in list of un-necessary eles 45 // - return final element of un-necessary list 46 47 vector<vector<int>> unnecessaryEdges {}; 48 49 // key = index of node 50 unordered_map<int, Node*> nodes {}; 51 52 for(auto edge: edges) { 53 if(nodes[edge[0]] == nullptr) { 54 nodes[edge[0]] = new Node(); 55 nodes[edge[0]]->identifier = edge[0]; 56 } 57 if(nodes[edge[1]] == nullptr) { 58 nodes[edge[1]] = new Node(); 59 nodes[edge[1]]->identifier = edge[1]; 60 } 61 } 62 63 for(auto edge: edges) { 64 65 auto n1 = nodes[edge[0]]; 66 auto n2 = nodes[edge[1]]; 67 68 bool joined = union_sets(n1,n2); 69 if(not joined) { 70 unnecessaryEdges.push_back(edge); 71 } 72 } 73 74 if(unnecessaryEdges.size() > 0) { 75 return unnecessaryEdges[unnecessaryEdges.size() - 1]; 76 } 77 else { 78 return vector<int>{}; 79 } 80 81 } 82 };