Computing a partition of S from maximal cliques