Universidade Federal de Minas Gerais
Instituto de Ciências Exatas
Departamento de Ciência da Computação

Algoritmos e Estruturas de Dados I

#include <stdio.h>
#include <stdlib.h>

//https://oeis.org/A006905
//A006905 Number of transitive relations on n labeled nodes.
//1=2, 2=13, 3=171, 4=3994, 5=154303, ...

int isTransitive(int N, int r[][N]){
int ii,jj,kk;
for(ii=0; ii<N; ii++)
for(jj=0; jj<N; jj++)
for(kk=0; kk<N; kk++)
if(r[ii][jj]&&r[jj][kk]) if(!r[ii][kk]) return 0;
return 1;
}

void gera(int N, int mq[][N], int ordem){
int ii, jj;
for(ii=0; ii<N; ii++)
for(jj=0; jj<N; jj++){
mq[ii][jj]=ordem&1; ordem=ordem>>1;
}
}

void escreve(int N, int m[][N]){
int ii, jj;
for(ii=0; ii<N; ii++){
for(jj=0; jj<N; jj++) printf(m[ii][jj]?"1 ":"0 ");
printf("\n");
}
}

int main(int argc, char *argv[]){
printf("Entre com numero de elementos:");
int ne;
scanf("%d", &ne);
int r[ne][ne];
int cntRel;
int totalRel;
totalRel=1<<ne*ne;
int notTrans=0;
for(cntRel=0; cntRel<totalRel; cntRel++){
gera(ne, r, cntRel);
if(!isTransitive(ne, r)){ notTrans++; escreve(ne,r); printf("\n");}
};
printf("Das %d relacoes %d sao transitivas (%d nao sao transitivas).\n",
totalRel, totalRel-notTrans, notTrans);
system("PAUSE");
return 0;
}