You are adding $$$k^2$$$ edges for each group, where $$$k \leq n$$$, so your memory complexity (and time complexity) is $$$O(n^2)$$$. You only need to connect adjacent vertices i.e $$$k - 1$$$ edges for each group.