Skip to content

Instantly share code, notes, and snippets.

@luccasiau
Created May 9, 2015 17:51
Show Gist options
  • Save luccasiau/9f3d4bc61938d6ee2d75 to your computer and use it in GitHub Desktop.
Save luccasiau/9f3d4bc61938d6ee2d75 to your computer and use it in GitHub Desktop.
// declarar a tabela
ancestral[MAXN][MAXL]; // MAXL representa lg N (com uma margem a mais, claro)
// primeiro, inicializamos tudo para -1
for(int i = 0;i < MAXN;i++)
for(int j = 0;j < MAXL;j++)
ancestral[i][j] = -1;
// definimos os pais de carda vértice
for(int i = 1;i <= N;i++) ancestral[i][0] = pai[i];
// montamos o restante da tabela com programação dinâmica
for(int j = 1;j < MAXL;j++)
for(int i = 1;i <= N;i++)
if(ancestral[i][j-1] != -1)
ancestral[i][j] = ancestral[ ancestral[i][j-1] ][j-1];
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment