I write me c++ solution using stranded unionfind with "balance" feature (with a rank). It passed first time. However, after few days when I trying to solve this problem again. I got a TLE at the 1, 10000 test case. I have cope paste some of the top rank post int c++ language. they actually slow than mine. (and also got a TLE). I do not know why? I saw the Java solution with the same idea only takes 15ms.
Passed before but get a TLE now


class Solution { struct Node { pair<int, int> parent; int height; Node():parent(1,1), height(1) {} }; // get_parent node; inline Node * get_parent (Node** ptable, Node* cur) { return &ptable[cur>parent.first][cur>parent.second]; } inline bool is_empty(Node *n) { return n>parent.first == 1; } // find Node * find(Node** ptable, int i, int j) { Node * cur = &ptable[i][j]; if (!is_empty(cur)) { Node * next = cur; do { cur = next; next = get_parent(ptable, cur); } while (cur != next); } return cur; } // merge, this should be called when non of the node is (1,1) Node * merge(Node**ptable, Node*n1, Node*n2, int &count) { if (n1 == n2  is_empty(n2)) { return n1; } count; if (n1>height < n2>height) { n1>parent = n2>parent; return n2; } else if (n1>height > n2>height) { n2>parent = n1>parent; return n1; } else { n2>height++; n1>parent = n2>parent; return n2; } } public: vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) { Node** ptable = new Node*[m]; for (int i=0; i<m; ++i) { ptable[i] = new Node[n]; } vector<int> res; res.reserve(positions.size()); int count=0; Node * n1, n2; for (const pair<int, int> &p : positions) { int i=p.first; int j=p.second; n1 = find(ptable, i, j); if (!is_empty(n1)) { res.push_back(count); continue; } count++; // set to itsefl n1>parent.first = i; n1>parent.second = j; // ^v<>; if (i>0) n1 = merge(ptable, n1, find(ptable, i1, j), count); if (i+1<m) n1 = merge(ptable, n1, find(ptable, i+1, j), count); if (j>0) n1 = merge(ptable, n1, find(ptable, i, j1), count); if (j+1<n) merge(ptable, n1, find(ptable, i, j+1), count); res.push_back(count); } for (int i = 0; i<m; ++i) { delete [] ptable[i]; } delete [] ptable; return res; } };