I'm practicing solving programming problems in free time. This problem I spotted some time ago and still don't know how to solve it:
For a given undirected graph with $n$ vertices and $m$ edges (both less than $2\cdot 10 ^6$) I need to split its vertices into as many groups as possible, but with two conditions: each pair of vertices from different groups are connected by an edge and each vertex is in exactly one group. At the end I need to know the size of each group.
I was proud when I came up with this solution: consider complemented graph of the original graph and use Disjoint-set data structure for it. When we finish, we will have some connected components which are the answer. I think I can prove this. But, even if, it's only theoretical solution. With given constraints it's very very bad, not optimal(complemented graph can be huge with such $n$). But I believe this approach can be somehow smartly fixed. But how? I heard that this problem can be solved in $O((n+m)\log n)$ time.
Can anyone help?
For a graph with vertices indexed from $1$ to $7$ and $16$ edges:
1 3
1 4
1 5
2 3
3 4
4 5
4 7
4 6
5 6
6 7
2 4
2 7
2 5
3 5
3 7
1 7
we have $3$ groups with sizes: $1$, $2$ and $4$.
These groups are: $\left\{4\right\}, \ \left\{5,7\right\}, \ \left\{1,2,3,6\right\}$ respectively. There are edges connecting each pair of vertices from different groups and we can't create more groups.