K-Arboles

karboles.cpp

#include<iostream>
#include<list>
#define MAXN 100005
#define MAXM 505
using namespace std;
int padre[MAXN],N,M,k=0;
bool prohibido[MAXN][MAXM];
int colores[MAXN];
int inorder[MAXN];
list<int> hijos[MAXN];

bool color(int n){
    if(n==N){
        return true;
    }
    int m=inorder[n];
    bool t=false;
    colores[m]=0;
    while(colores[m]<M){
        if((!prohibido[m][colores[m]])&&(colores[m]!=colores[padre[m]])){
            t=color(n+1);
        }
        if(t){
            return t;
        }
        else if(colores[m]!=colores[padre[m]]){
            prohibido[m][colores[m]]=1;
        }
        colores[m]++;
    }
    return false;
}

void inord(int n){
    list<int>::iterator it;
    inorder[k]=n;
    for(it=hijos[n].begin();it!=hijos[n].end();it++){
        k++;
        inord(*it);
    }
}

int main(){
    int i,C,a,b;
    cin >> N >> M;
    padre[0]=MAXN-1;
    colores[MAXN-1]=-1;
    for(i=1;i<N;i++){
        cin >> padre[i];
        hijos[padre[i]].push_front(i);
    }
    cin >> C;
    for(i=0;i<C;i++){
        cin >> a >> b;
        prohibido[a][b]=true;
    }
    inord(0);
    if(color(0)){
        for(i=0;i<N;i++){
            cout << colores[i] << endl;
        }
    }
    else{
        cout << -1;
    }
    return 0;
}