Grafos

Contents

1. Grafos. 1.1. Busquedas 1.2. DAGs 1.3. Arbol de expansion Minima. 1.4. Caminos mas cortos. 1.5. Flujos en Redes (Network Flow). 1.6. Otros Problemas. 1.7. Teoria de Grafos. 2.Programacion Dinamica. 2.1. LCS. 2.2. LIS (nlogk). 2.3. Multiplicacion optima de matrices. 2.4. Edit Distance. 2.5. Coin Change. 2.6. Knapsack 0-1 (Mochila). 2.7. KMP (String Matching). 2.8. Problema delcartero chino (Chinese Postman Problem). 3. Estructuras de datos. 3.1. Hashing (para cadenas). 3.2. Estructura Union-Find. 3.3. Funcion para suma de dos strings. 3.4. Funcion para multiplicacion de dosstrings. 3.5. BigInteger 4. Busqueda y Ordenamiento. 4.1. MergeSort 4.2. Busqueda Binaria. 5. Geometria. 5.1. Geometria Clasica. 5.2. Geometria Computacional. 6. Teoria de Numeros. 6.1. AritmeticaModular 6.2. Exponenciacion rapida. 6.3. Factorizacion prima de un entero. 6.4. GCD Extendido 6.5. Criba de Eratostenes. 6.6. Funcion Phi de Euler (Numero de primos relativos a un numero). 6.7. Formulas yteoremas utiles 7. Combinatoria. 7.1. Combinaciones. 7.2. Resolucion de Recurrencias Lineales usando Exponenciacion de una matriz (QMatrix). 7.3. Conteo. 7.4. Formulas utiles. 7.5. GeneracionCombinatoria 8. Otros.

1 1 3 3 4 4 8 8 8 8 8 8 8 9 9 9 9 10 10 10 11 11 11 12 12 12 12 12 14 20 20 20 20 20 20 21 21 22 22 23 23 23 23 23

1. Grafos. 1.1. Busquedas. 1.1.1. DFS y BFS.
int parent[MAX];int seen[MAX];

2

bool BFS(int s, int t) { queue q; memset(seen, 0, sizeof(seen)); parent[s] = -1; seen[s] = 1; q.push( s ); while(!q.empty()) { s = q.front(); q.pop(); if (s == t) break; for(int i=0; i 0) parent[i] = s, q.push( i ); } return seen[t] != 0;

}

1.1.2. Deteccion de puntos de articulacion (Articulation Points).
int tim; bool artic[MV]; int d[MV]; int low[MV]; int seen[MV];int parent[MV]; void dfs(int x){ seen[x]=1; low[x]=d[x]=tim++; for(int i=0;ilow[ady[x][i]]) low[x]=low[ady[x][i]]; if(low[ady[x][i]]>=d[x]) artic[x]=true; }else if(ady[x][i]!=parent[x])

low[x]