Topological Sort vs Union Find

Courses: 0 -> 1 -> 2

// java
// time = O(n log n) (path halving only; O(n * α(n)) needs union by size/rank too), space = O(n)
// IDEA: union-find view -> a tree is "n nodes, no node with 2 parents,
//       no edge that closes a cycle, and exactly 1 component at the end"
// LC 1361 - Validate Binary Tree Nodes  (approach 1: union-find)
class SolutionUF {
    int[] parent;

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];   // path compression
            x = parent[x];
        }
        return x;
    }

    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        int[] indeg = new int[n];
        int components = n;

        for (int i = 0; i < n; i++) {
            for (int child : new int[]{ leftChild[i], rightChild[i] }) {
                if (child == -1) continue;
                if (++indeg[child] > 1) return false;   // 2 parents -> not a tree
                int ru = find(i), rv = find(child);
                if (ru == rv) return false;             // edge closes a cycle
                parent[rv] = ru;
                components--;
            }
        }
        return components == 1;                          // forest -> false
    }
}

// java
// time = O(n), space = O(n)
// IDEA: topological / indegree view -> exactly one indegree-0 root,
//       then a BFS from that root must reach all n nodes
// LC 1361 - Validate Binary Tree Nodes  (approach 2: indegree + BFS)
class SolutionTopo {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] indeg = new int[n];
        for (int i = 0; i < n; i++) {
            if (leftChild[i]  != -1 && ++indeg[leftChild[i]]  > 1) return false;
            if (rightChild[i] != -1 && ++indeg[rightChild[i]] > 1) return false;
        }

        int root = -1;
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                if (root != -1) return false;   // 2+ roots -> forest
                root = i;
            }
        }
        if (root == -1) return false;           // no root -> cycle

        Deque<Integer> q = new ArrayDeque<>();
        q.offer(root);
        int seen = 0;
        while (!q.isEmpty()) {
            int cur = q.poll();
            seen++;
            if (leftChild[cur]  != -1) q.offer(leftChild[cur]);
            if (rightChild[cur] != -1) q.offer(rightChild[cur]);
        }
        return seen == n;                        // unreached nodes -> cycle / forest
    }
}

# python
# time = O(n log n) (path halving only; O(n * α(n)) needs union by size/rank too), space = O(n)
# IDEA: union-find view -> reject a 2nd parent, reject a cycle-closing edge,
#       then require exactly 1 remaining component
# LC 1361 - Validate Binary Tree Nodes  (approach 1: union-find)
class SolutionUF:
    def validateBinaryTreeNodes(self, n, leftChild, rightChild):
        parent = list(range(n))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]   # path compression
                x = parent[x]
            return x

        indeg = [0] * n
        components = n

        for i in range(n):
            for child in (leftChild[i], rightChild[i]):
                if child == -1:
                    continue
                indeg[child] += 1
                if indeg[child] > 1:
                    return False                # 2 parents -> not a tree
                ru, rv = find(i), find(child)
                if ru == rv:
                    return False                # edge closes a cycle
                parent[rv] = ru
                components -= 1

        return components == 1                  # forest -> False

# python
# time = O(n), space = O(n)
# IDEA: topological / indegree view -> exactly one indegree-0 root,
#       then BFS from it must visit all n nodes
# LC 1361 - Validate Binary Tree Nodes  (approach 2: indegree + BFS)
from collections import deque

class SolutionTopo:
    def validateBinaryTreeNodes(self, n, leftChild, rightChild):
        indeg = [0] * n
        for i in range(n):
            for child in (leftChild[i], rightChild[i]):
                if child == -1:
                    continue
                indeg[child] += 1
                if indeg[child] > 1:
                    return False

        root = -1
        for i in range(n):
            if indeg[i] == 0:
                if root != -1:
                    return False       # 2+ roots -> forest
                root = i
        if root == -1:
            return False               # no root -> cycle

        q, seen = deque([root]), 0
        while q:
            cur = q.popleft()
            seen += 1
            for child in (leftChild[cur], rightChild[cur]):
                if child != -1:
                    q.append(child)
        return seen == n

// java
// time = O(n log n) (path halving only; O(n * α(n)) needs union by size/rank too), space = O(n)
// IDEA: 1) scan for a node with 2 parents -> remember cand1 (1st edge) & cand2 (2nd edge)
//       2) union all edges EXCEPT cand2. A cycle now means cand2 was innocent:
//          answer is cand1 (if it exists) else the cycle edge. No cycle -> cand2.
// LC 685 - Redundant Connection II
class Solution {
    private int find(int[] p, int x) {
        while (p[x] != x) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }

    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        int[] parentOf = new int[n + 1];        // parent recorded in the INPUT
        int[] cand1 = null, cand2 = null;

        for (int[] e : edges) {
            int u = e[0], v = e[1];
            if (parentOf[v] != 0) {             // v already had a parent
                cand1 = new int[]{ parentOf[v], v };
                cand2 = e;
            } else {
                parentOf[v] = u;
            }
        }

        int[] p = new int[n + 1];
        for (int i = 0; i <= n; i++) p[i] = i;

        for (int[] e : edges) {
            if (e == cand2) continue;           // tentatively drop the 2nd parent edge
            int ru = find(p, e[0]), rv = find(p, e[1]);
            if (ru == rv) return (cand1 == null) ? e : cand1;   // case B / case C
            p[rv] = ru;
        }
        return cand2;                            // case A
    }
}

# python
# time = O(n log n) (path halving only; O(n * α(n)) needs union by size/rank too), space = O(n)
# IDEA: 1) find a node with 2 parents -> cand1 (1st edge), cand2 (2nd edge)
#       2) union everything except cand2; a cycle means cand2 was innocent
#          -> answer cand1 if it exists else the cycle edge; no cycle -> cand2
# LC 685 - Redundant Connection II
class Solution:
    def findRedundantDirectedConnection(self, edges):
        n = len(edges)
        parent_of = [0] * (n + 1)          # parent recorded in the INPUT
        cand1 = cand2 = None

        for u, v in edges:
            if parent_of[v]:               # v already had a parent
                cand1, cand2 = [parent_of[v], v], [u, v]
            else:
                parent_of[v] = u

        p = list(range(n + 1))

        def find(x):
            while p[x] != x:
                p[x] = p[p[x]]
                x = p[x]
            return x

        for e in edges:
            if e == cand2:                 # tentatively drop the 2nd parent edge
                continue
            ru, rv = find(e[0]), find(e[1])
            if ru == rv:                   # case B / case C
                return e if cand1 is None else cand1
            p[rv] = ru
        return cand2                       # case A