Divide Nodes Into the Maximum Number of Groups solution and explanation

def maxGroups(n, edges):
    from collections import deque, defaultdict

    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    
    def bfs(start):
        queue = deque([(start, 0)])
        depths = {}
        heights = 0
        while queue:
            node, depth = queue.popleft()
            if node in depths:
                if depths[node] != depth:
                    return -1
            else:
                depths[node] = depth
                for neighbor in graph[node]:
                    queue.append((neighbor, depth + 1))
            heights = max(heights, depth)
        return heights

    seen = set()
    max_height = 0
    for node in range(1, n + 1):
        if node not in seen:
            height = bfs(node)
            if height == -1:
                return -1
            max_height = max(max_height, height)
            seen.update(depths.keys())

    return max_height + 1

import java.util.*;

public class MaxGroups {
    public int maxGroups(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            int a = edge[0], b = edge[1];
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        int maxHeight = 0;
        boolean[] visited = new boolean[n + 1];
        int[] color = new int[n + 1];
        Arrays.fill(color, -1);

        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                int height = bfs(i, graph, visited, color);
                if (height == -1) {
                    return -1;
                }
                maxHeight = Math.max(maxHeight, height);
            }
        }

        return maxHeight + 1;
    }

    private int bfs(int node, List<List<Integer>> graph, boolean[] visited, int[] color) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{node, 0});
        visited[node] = true;
        int maxDepth = 0;
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int u = current[0], depth = current[1];
            color[u] = depth % 2;
            maxDepth = Math.max(maxDepth, depth);

            for (int v : graph.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    queue.offer(new int[]{v, depth + 1});
                } else if (color[v] == color[u]) {
                    return -1;
                }
            }
        }

        return maxDepth;
    }
}

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int maxGroups(int n, vector<vector<int>>& edges) {
    vector<vector<int>> graph(n + 1);
    for (auto &edge : edges) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }

    vector<int> color(n + 1, -1);
    int maxHeight = 0;

    for (int i = 1; i <= n; ++i) {
        if (color[i] == -1) { // unvisited
            stack<pair<int, int>> s;
            s.push({i, 0});
            int height = 0;
            while (!s.empty()) {
                auto [node, depth] = s.top();
                s.pop();
                color[node] = depth % 2;
                height = max(height, depth);
                for (int neighbor : graph[node]) {
                    if (color[neighbor] == -1) {
                        s.push({neighbor, depth + 1});
                    } else if (color[neighbor] == color[node]) {
                        return -1;
                    }
                }
            }
            maxHeight = max(maxHeight, height);
        }
    }
    return maxHeight + 1;
}

function maxGroups(n, edges) {
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [a, b] of edges) {
        graph[a].push(b);
        graph[b].push(a);
    }

    const color = new Array(n + 1).fill(-1);
    let maxHeight = 0;

    function dfs(node, depth) {
        const stack = [[node, depth]];
        let currentHeight = 0;
        while (stack.length) {
            const [u, depth] = stack.pop();
            color[u] = depth % 2;
            currentHeight = Math.max(currentHeight, depth);
            for (const v of graph[u]) {
                if (color[v] === -1) {
                    stack.push([v, depth + 1]);
                } else if (color[v] === color[u]) {
                    return -1;
                }
            }
        }
        return currentHeight;
    }

    for (let i = 1; i <= n; ++i) {
        if (color[i] === -1) {
            const height = dfs(i, 0);
            if (height === -1) return -1;
            maxHeight = Math.max(maxHeight, height);
        }
    }

    return maxHeight + 1;
}

func magnificentSets(n int, edges [][]int) (ans int) {
	g := make([][]int, n)
	for _, e := range edges {
		a, b := e[0]-1, e[1]-1
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	d := make([]int, n)
	for i := range d {
		q := []int{i}
		dist := make([]int, n)
		dist[i] = 1
		mx := 1
		root := i
		for len(q) > 0 {
			a := q[0]
			q = q[1:]
			root = min(root, a)
			for _, b := range g[a] {
				if dist[b] == 0 {
					dist[b] = dist[a] + 1
					mx = max(mx, dist[b])
					q = append(q, b)
				} else if abs(dist[b]-dist[a]) != 1 {
					return -1
				}
			}
		}
		d[root] = max(d[root], mx)
	}
	for _, x := range d {
		ans += x
	}
	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}