Number Of Ways To Reconstruct A Tree solution and explanation

class Solution:
    def checkWays(self, pairs):
        from collections import defaultdict
        import functools

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            rootX = find(x)
            rootY = find(y)
            if rootX != rootY:
                parent[rootY] = rootX

        nodes = set()
        for x, y in pairs:
            nodes.add(x)
            nodes.add(y)

        parent = {x: x for x in nodes}
        adjacency = defaultdict(set)
        degree = defaultdict(int)

        for x, y in pairs:
            adjacency[x].add(y)
            adjacency[y].add(x)
            degree[x] += 1
            degree[y] += 1

        for x, y in pairs:
            union(x, y)

        root_candidate = [x for x in nodes if degree[x] == len(nodes) - 1]

        if len(root_candidate) == 0:  # can't have a tree
            return 0
        if len(root_candidate) > 1:  # multiple trees possible
            return 2

        root = root_candidate[0]
        groups = defaultdict(set)
        for x in nodes:
            groups[find(x)].add(x)

        # Check if all nodes except root are connected to it through some path
        for key, group in groups.items():
            if root not in group and len(group) > 1:
                return 0

        return 1

var checkWays = function(pairs) {
    let adj = new Map();
    let degree = new Map();
    let nodes = new Set();

    for (let [u, v] of pairs) {
        if (!adj.has(u)) adj.set(u, new Set());
        if (!adj.has(v)) adj.set(v, new Set());

        adj.get(u).add(v);
        adj.get(v).add(u);

        degree.set(u, (degree.get(u) || 0) + 1);
        degree.set(v, (degree.get(v) || 0) + 1);
        nodes.add(u);
        nodes.add(v);
    }

    const roots = [];
    for (let node of nodes) {
        if (degree.get(node) === nodes.size - 1) {
            roots.push(node);
        }
    }

    if (roots.length > 1) return 2;
    if (roots.length === 0) return 0;

    const root = roots[0];

    const visited = new Set();
    const dfs = (node) => {
        visited.add(node);
        for (let neighbor of adj.get(node)) {
            if (!visited.has(neighbor)) {
                dfs(neighbor);
            }
        }
    };

    dfs(root);

    return visited.size === nodes.size ? 1 : 0;
};

import java.util.*;

public class Solution {
    public int checkWays(int[][] pairs) {
        Map<Integer, Set<Integer>> adj = new HashMap<>();
        Map<Integer, Integer> degree = new HashMap<>();
        Set<Integer> nodes = new HashSet<>();

        for (int[] pair : pairs) {
            adj.computeIfAbsent(pair[0], k -> new HashSet<>()).add(pair[1]);
            adj.computeIfAbsent(pair[1], k -> new HashSet<>()).add(pair[0]);
            degree.put(pair[0], degree.getOrDefault(pair[0], 0) + 1);
            degree.put(pair[1], degree.getOrDefault(pair[1], 0) + 1);
            nodes.add(pair[0]);
            nodes.add(pair[1]);
        }

        List<Integer> possibleRoots = new ArrayList<>();
        for (int node : nodes) {
            if (degree.get(node) == nodes.size() - 1) {
                possibleRoots.add(node);
            }
        }

        if (possibleRoots.size() == 0) return 0;
        if (possibleRoots.size() > 1) return 2;

        int root = possibleRoots.get(0);
        Set<Integer> visited = new HashSet<>();

        dfs(root, adj, visited);

        return visited.size() == nodes.size() ? 1 : 0;
    }

    private void dfs(int node, Map<Integer, Set<Integer>> adj, Set<Integer> visited) {
        visited.add(node);
        for (int neighbor : adj.get(node)) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor, adj, visited);
            }
        }
    }
}

#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

class Solution {
public:
    int checkWays(vector<vector<int>>& pairs) {
        unordered_map<int, unordered_set<int>> adj;
        unordered_map<int, int> degree;
        unordered_set<int> nodes;

        for (auto& pair : pairs) {
            adj[pair[0]].insert(pair[1]);
            adj[pair[1]].insert(pair[0]);
            degree[pair[0]]++;
            degree[pair[1]]++;
            nodes.insert(pair[0]);
            nodes.insert(pair[1]);
        }

        vector<int> roots;
        for (auto& node : nodes) {
            if (degree[node] == nodes.size() - 1) {
                roots.push_back(node);
            }
        }

        if (roots.empty()) return 0;
        if (roots.size() > 1) return 2;

        int root = roots[0];
        unordered_set<int> visited;
        dfs(root, adj, visited);

        return visited.size() == nodes.size() ? 1 : 0;
    }

private:
    void dfs(int node, unordered_map<int, unordered_set<int>>& adj, unordered_set<int>& visited) {
        visited.insert(node);
        for (auto& neighbor : adj[node]) {
            if (visited.find(neighbor) == visited.end()) {
                dfs(neighbor, adj, visited);
            }
        }
    }
};

func checkWays(pairs [][]int) int {
	g := make([][]bool, 510)
	v := make([][]int, 510)
	for i := range g {
		g[i] = make([]bool, 510)
	}
	for _, p := range pairs {
		x, y := p[0], p[1]
		g[x][y] = true
		g[y][x] = true
		v[x] = append(v[x], y)
		v[y] = append(v[y], x)
	}
	var nodes []int
	for i := 1; i <= 500; i++ {
		if len(v[i]) > 0 {
			nodes = append(nodes, i)
			g[i][i] = true
		}
	}
	sort.Slice(nodes, func(i, j int) bool {
		return len(v[nodes[i]]) < len(v[nodes[j]])
	})
	equal := false
	root := 0
	for i, x := range nodes {
		j := i + 1
		for ; j < len(nodes) && !g[x][nodes[j]]; j++ {
		}
		if j < len(nodes) {
			y := nodes[j]
			if len(v[x]) == len(v[y]) {
				equal = true
			}
			for _, z := range v[x] {
				if !g[y][z] {
					return 0
				}
			}
		} else {
			root++
		}
	}
	if root > 1 {
		return 0
	}
	if equal {
		return 2
	}
	return 1
}