eso.cpp

#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <deque>
#include <string>
#include <math.h>

using namespace std;

class Nodo{
    public:
        bool tonda;
        deque<int> num;
        deque<class Nodo*> succ;
};

// costrusco ricorsivamente l'albero della sequenza passata per parametro e ritorno un puntatore alla radice al main
Nodo* insert(int vet[], int s, int e){

    Nodo* node;
    node = new Nodo();

    if(vet[s] == -1)
        node->tonda = true;
    else
        node->tonda = false;

    node->num.resize(0);
    s++;
    e--;

    int i;
    int neg = -5;
    for(i=s; i<=e; i++)
        if(vet[i] > 0)
            node->num.push_back(vet[i]);
        else{
            int par = 1;
            int _s = i;
            int _e;
            while(par != 0){

                i++;
                if(vet[i] == -1 || vet[i] == -3)
                    par++;
                else
                    if(vet[i] == -2 || vet[i] == -4)
                        par--;
            }
            _e = i;
            node->succ.push_back(insert(vet, _s, _e));
            node->num.push_back(neg);
            neg--;
        }

    return node;
}
/*
void visit(Nodo* node, int num){
    printf("\n<%d> %d:\t",node->tonda, num);
    for(int i=0; i<node->num.size(); i++)
        printf("%4d", node->num[i]);

    for(int i=0; i<node->succ.size(); i++)
        visit(node->succ[i], 0-i-5);
}
*/

// costruisco la sequenza senza parentesi e la ritorno al main
deque<int> getSeq(Nodo* node){

    deque<int> out;

    for(int i=0; i<node->num.size(); i++)
        if(node->num[i] >= 0)
            out.push_back(node->num[i]);
        else{
            deque<int> t = getSeq(node->succ[0-node->num[i]-5]);
            for(int j=0; j<t.size(); j++)
                out.push_back(t[j]);
        }


    return out;
}

// ordino tutte le sequenze di numeri dei nodi
void order(Nodo* node){

    // se la parentesi è tonda ordino tutto in modo crescente
    if(node->tonda)
        sort(node->num.begin(), node->num.end());
    else
        // altrimenti la parentesi è quadra, e se il primo numero è maggiore dell'ultimo ribalto la sequenza
        if(node->num.size() > 1)
            if(node->num[0] > node->num[node->num.size()-1]){
                for(int i=0; node->num.size()-i-1 > i; i++)
                    swap(node->num[i], node->num[node->num.size()-i-1]);
            }

    // ordino tutti i sottonodi
    for(int i=0; i<node->succ.size(); i++)
        order(node->succ[i]);

}

main(){
    FILE *pF = fopen("input.txt","r");
    int n,m;
    fscanf(pF,"%d %d",&n,&m);

    int i,j,c;
    int vet[m];

    deque<class Nodo*> eso;

    for(c=0;c<n;c++){
        fscanf(pF,"\n%d",&vet[0]);
        for(j=1;j<m;j++)
            fscanf(pF," %d",&vet[j]);

        // costruisco l'albero
        eso.push_back(insert(vet, 0, m-1));

    }
    fclose(pF);


    deque<deque<int> > ris;
    for(i=0; i<eso.size(); i++){
        // ordino l'albero
        order(eso[i]);
        // costruisco le sequenze ordinate
        ris.push_back(getSeq(eso[i]));
    }


    // count[i] contiente il numero delle sequenze uguali alla (i+1)^ sequenza compresa se stessa
    int count[n];
    for(i=0; i<n; i++)
        count[i] = 0;

    // lista delle posizioni delle sequenze uguali alla (i+1)^ sequenza compresa se stessa
    deque<deque<int> > position(n);
    position[0].push_back(1);
    count[0] = 1;
    int flag;

    // per tutte le sequenze tranne la prima
    for(i=1; i<ris.size(); i++){
        // controllo se è uguale a una delle sequenze precedenti
        for(j=0; j<i; j++){

            flag = 1;

            for(c=0; c<ris[i].size(); c++)
                if(ris[i][c] != ris[j][c]){
                    flag = 0;
                    break;
                }

            // se si incremento count e aggiungo la posizione alla lista
            if(flag){
                count[j]++;
                position[j].push_back(i+1);
                break;
            }

        }

        // altrimenti creo un nuovo gruppo
        if(!flag){
            count[i]++;
            position[i].push_back(i+1);
        }

    }

    pF = fopen("output.txt", "w");
    c = 0;
    for(i=0; i<n; i++)
        if(count[i] > 0)
            c++;
    fprintf(pF, "%d", c);
    for(i=0; i<n; i++)
        if(count[i] > 0){
            fprintf(pF, "\n%d", count[i]);
            for(j=0; j<position[i].size(); j++)
                fprintf(pF, " %d", position[i][j]);
        }
    fclose(pF);
}