<repo_name>jefersonla/LABII-Listas<file_sep>/Lista_VII/INTERMLG.cpp
#include <iostream>
#include <queue>
#include <list>
#include <limits>
#include <set>
#include <cmath>
#include <cstdio>

#define MAX_NUM_VERTICES 1001
#define BRANCO 0
#define CINZA  1
#define PRETO  2

/* For each */
#define for_each(member,container)  for(typeof(container.begin())   member  = container.begin(); \
                                                                    member != container.end();   \
                                                                    member ++ )

/* better find */
#define not_found_in(var)   var.end()

/* Max value between two vars */
#define max_2(var1, var2)     (var1 > var2 ? var1 : var2)
#define min_2(var1, var2)     (var1 < var2 ? var1 : var2)

/* Verifica a existência */
#define is_none(var)        (var == NULL)
#define is_not_none(var)    (var != NULL)

/* Valor infinito */
#define INFINITY_VALUE std::numeric_limits<int>::max()
            
/* Indice nulo */
#define NULO -1

// APENAS PARA PROPOSITOS DE DEBUG
//#define DEBUG

using namespace std;

/* Estrutura do grafo - arestas e vertices */
int grafo[MAX_NUM_VERTICES][MAX_NUM_VERTICES];
pair<long double, long double> vertices[MAX_NUM_VERTICES];

/* Matrizes do Floyd Warshall */
long double dist[MAX_NUM_VERTICES][MAX_NUM_VERTICES] = {{ 0 }};
int parente[MAX_NUM_VERTICES][MAX_NUM_VERTICES] = {{ 0 }};
int pai[MAX_NUM_VERTICES] = { 0 };

/* Variaveis do programa */
int N, M;

struct compare
{
    bool operator ()(const pair<pair<int, int>, int>&i, const pair<pair<int, int>, int>&j){
        return i.second <= j.second;
    };
};

/* Distância de u a v */
#define w(u, v) (dist[u][v])

/* Define a união dos parentes */
#define union(u, v) pai[u] = pai[v]

/* Retorna o valor máximo do set */
#define max_value_set(XX) XX.rbegin()->second

/* Procura o parente de um dado vértice */
int find_set(int v){
    if(v != pai[v])
        pai[v] = find_set(pai[v]);
    return pai[v];
}

/* Arvore geradora minima do Kruskal */
set<pair<pair<int,int>,long double>, compare> A;

long double Kruskal(){
    /* Pair de cordenadas e custo modelo: <<u,v>, custo>, e ordenamos o mesmo pelo custo */
    set<pair<pair<int,int>,long double>, compare> Q;

    /* Insere no set a lista de pares e custo */
    for(int u = 1; u <= N; u++){
        for(int v = 1; v <= N; v++){
            if(grafo[u][v] != 0){
                Q.insert(make_pair(make_pair(u, v), w(u,v)));
#ifdef DEBUG
                cout << "u -- " << u << " | v -- " << v << " | w -- " << w(u,v) << endl;
#endif                
            }
        }
    }

#ifdef DEBUG
    /* Imprime todos os nós - deve estar ordenado pelo peso */
    cout << "Todas arestas" << endl;
    for_each(it, Q){
        int u = it->first.first;
        int v = it->first.second;
        int w = it->second;
        cout << "u " << u << " v " << v << " w " << w << endl;   
    }
#endif

    /* While n of nodes is different of 0 */
    int n_nodes = 0;
    long double soma = 0;
    for_each(it, Q){
        /* Pega os pares u e v da lista */
        int u = it->first.first;
        int v = it->first.second;

        /* Executa o find_set para os nós u e v */
        int find_set_u = find_set(u);
        int find_set_v = find_set(v);
        
        /* Se o pai de u for diferente do pai de v */
        if(find_set_u != find_set_v){
            A.insert(*it);
            soma += it->second;
            union(find_set_u, find_set_v);
        }

        /* Se já temos nossa arvore geradora minima paramos a execução */
        if(A.size() == (N - 1)){
            break;
        }
    }

#ifdef DEBUG
    /* Imprime todos os nós da nossa arvore geradora minima */
    cout << "Arvore geradora minima" << endl;
    for_each(it, A){
        int u = it->first.first;
        int v = it->first.second;
        int w = it->second;
        cout << "u " << u << " v " << v << " w " << w << endl;   
    }
#endif

    return soma;
}

int main(){
    long double x, y;
    int z = 1;

    while(true){
        cin >> N;

        if(N == 0)
            break;

        /* Inicalização do grafo */
        A.clear();
        for(int i = 1; i <= N; i++){
            /* Arestas & Distâncias & Caminho */
            for(int j = 1; j <= N; j++){
                dist[i][j] = INFINITY_VALUE;
                grafo[i][j] = 0;
                parente[i][j] = NULO;
            }

            /* Distâncias & Parentes na Diagonal */
            dist[i][i] = 0;
            parente[i][i] = i;
            pai[i] = i;
        }

        /* Lê as arestas */
        for(int i = 1; i <= N; i++){
            /* Pega os valores de A e B*/
            cin >> x;
            cin >> y;

            vertices[i] = make_pair(x, y);
        }

        for(int u = 1; u <= N; u++){
            for(int v = 1; v <= N; v++){
                /* Como temos um grafo não direcionado os dois caminhos são válidos */
                grafo[u][v] += 1;
                grafo[v][u] += 1;

                /* Cordenadas de u */
                long double xu = vertices[u].first;
                long double yu = vertices[u].second;

                /* Coordenadas de v */
                long double xv = vertices[v].first;
                long double yv = vertices[v].second;

                /* Custo de u a v atual for maior que o custo novo substitui */
                long double w_u_v = sqrt(pow(xu-xv, 2) + pow(yu-yv, 2));
                dist[u][v] = w_u_v;
                dist[v][u] = w_u_v;

                /* Menor caminho de u a v */
                parente[u][v] = u;
                parente[v][u] = v;
            }
        }

        /* Iremos construir uma arvore geradora minima usando Kruskal, e
           retornar o custo do menor caminho entre todos os nós */
        long double retorno = Kruskal();

        /* Não estamos interessado no custo total mas sim no menor valor que garante que haja um caminho
           direto ou indireto entre todos os nós. Se só existe um nó então retornamos 0, caso exista mais
           que um retornamos o valor máximo da nossa Arvore Geradora Minima no caso o set de A */
        if(N == 1){
            printf("%.4f\n", 0.0);
        }
        else{
            printf("%.4Lf\n", max_value_set(A));
        }
    }

    return 0;
}
<file_sep>/Lista_VI/PEDAGIO.cpp
#include <iostream>
#include <queue>
#include <limits>

#define INFINITY_VALUE std::numeric_limits<int>::max()
#define MAX_NUM_VERTICES 51
#define UNDEFINED_VERTICE -1

/* Como a distância é fixa entre os nós distancia de u a v é 1 */
#define distancia(u,v) 1

using namespace std;

typedef struct VerticeStruct{
	int num;
	int distancia;
	int anterior;
} Vertice;

int grafo[MAX_NUM_VERTICES][MAX_NUM_VERTICES] = {{0}};
int menor_caminho[MAX_NUM_VERTICES];
Vertice vertices[MAX_NUM_VERTICES];

int C, L, E, P;

void dijkstra(){
	/* Criamos uma fila de prioridades */
	priority_queue<pair<int, int> > Q;

	/* Adicionamos o vértice de origem */
	Q.push(make_pair(0, L));

	/* Enquanto nossa fila não estiver vazia */
	while(!Q.empty()){
		/* Extraimos o menor vertice de nossa fila */
		Vertice *u = &vertices[Q.top().second];
		Q.pop();

		/* Para cada vizinho v de u */
		for(int i = 1; i <= C; i++){
			Vertice *v = &vertices[i];
			/* Se o vertice u é vizinho de v */
			if(grafo[u->num][v->num] > 0){
				/* Some a distancia de u com a distancia de u a v
				como temos que a distância é fixa, ela é igual a 1 */
				int alternativa = u->distancia + distancia(u, v);
				/* Se o novo caminho for o melhor caminho armazene ele */
				if (alternativa < v->distancia){
					v->distancia = alternativa;
					v->anterior = u->num;
					Q.push(make_pair(v->distancia, v->num));
				}
			}
		}
	}
}

int main(){
	int K = 1;

	do{
		/* Lê os quatro inteiros */
		cin >> C;
		cin >> E;
		cin >> L;
		cin >> P;

		/* Se condição de parada de execução for atingida */
		if((C == 0) && (E == 0) && (L == 0) && (P == 0)){
			break;
		}

		/* Inicialização dos vertices e arestas */
		for (int i = 1; i <= C; i++){
			for (int j = 1; j <= C; j++){
				grafo[i][j] = 0;
			}

			vertices[i].num = i;
			vertices[i].distancia = INFINITY_VALUE;
			vertices[i].anterior = UNDEFINED_VERTICE;
		}

		/* Sabemos que L é a cidade aonde estamos logo inicializamos esta distância */
		vertices[L].distancia = 0;

		/* Lê toda a entrada */
		for(int i = 0; i < E; i++){
			int O, D;
			cin >> O;
			cin >> D;
			grafo[O][D] += 1;
			grafo[D][O] += 1;
		}

		/* Agora iremos encontrar o melhor caminho de L até todos os nós adjacentes a L */
		dijkstra();

		if(K > 1){
			cout << endl;
		}

		cout << "Teste " << K << endl;

		/* Após descobrir o melhor caminho a partir de L iremos varrer todos os vértices
		e printar o menor caminho ou seja o caminho com no máximo P de distância */
		bool primeiro_elemento = true;
		for(int i = 1; i <= C; i++){
			Vertice *v = &vertices[i];
			if(v->num != L && v->distancia <= P){
				if(primeiro_elemento){
					cout << v->num;
					primeiro_elemento = false;
				}
				else{
					cout << " " << v->num;
				}
			}
		}

		/* Quebra a linha do caminho apresentado */
		cout << endl;
		K += 1;

	} while((C != 0) && (E != 0) && (L != 0) && (P != 0));

	return 0;
}<file_sep>/Lista_VI/DUENDE.cpp
#include <bits/stdc++.h>

#define INFINITY_VALUE std::numeric_limits<int>::max()
#define MAX_NUM_VERTICES (10 * 10 + 1)
#define UNDEFINED_VERTICE -1

/* Como a distância é fixa entre os nós distancia de u a v é 1 */
#define distancia(u,v) 1

using namespace std;

typedef struct VerticeStruct{
	int num;
	int distancia;
	int anterior;
} Vertice;

/* For each */
#define for_each(member,container) 	for(typeof(container.begin())   member  = container.begin();  \
									                                member != container.end();    \
                                                                    member ++ )

int grafo[MAX_NUM_VERTICES][MAX_NUM_VERTICES] = {{0}};
int menor_caminho[MAX_NUM_VERTICES];
Vertice vertices[MAX_NUM_VERTICES];

int N, L, M, T;

list<int> saidas;

int mapa[11][11] = {{ 0 }};


void dijkstra(){
	/* Criamos uma fila de prioridades */
	priority_queue<pair<int, int> > Q;

	/* Adicionamos o vértice de origem */
	Q.push(make_pair(0, L));

	/* Enquanto nossa fila não estiver vazia */
	while(!Q.empty()){
		/* Extraimos o menor vertice de nossa fila */
		Vertice *u = &vertices[Q.top().second];
		Q.pop();

		/* Para cada vizinho v de u */
		for(int i = 0; i < T; i++){
			Vertice *v = &vertices[i];
			/* Se o vertice u é vizinho de v */
			if(grafo[u->num][v->num] > 0){
				/* Some a distancia de u com a distancia de u a v
				como temos que a distância é fixa, ela é igual a 1 */
				int alternativa = u->distancia + distancia(u, v);
				/* Se o novo caminho for o melhor caminho armazene ele */
				if (alternativa < v->distancia){
					v->distancia = alternativa;
					v->anterior = u->num;
					Q.push(make_pair(v->distancia, v->num));
				}
			}
		}
	}
}

int main(){

	/* Lê os quatro inteiros */
	cin >> N;
	cin >> M;

	/* Total de vertices */
	T = N * M;

	/* Inicialização dos vertices e arestas */
	saidas.clear();
	for (int i = 0; i < T; i++){
		for (int j = 0; j < T; j++){
			grafo[i][j] = 0;
		}

		vertices[i].num = i;
		vertices[i].distancia = INFINITY_VALUE;
		vertices[i].anterior = UNDEFINED_VERTICE;
	}

	/* Lê todo o mapa */
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			int tipo;
			cin >> tipo;
			mapa[i][j] = tipo;

			if(tipo == 3){
				L = (i * M) + j;
			}
			else if(tipo == 0){
				saidas.push_back((i * M) + j);
			}
		}
	}
	
	/* Constroi o grafo com o mapa recebido */
	for(int i = 0; i < N; i++){
		for (int j = 0; j < M; j++){
			if(mapa[i][j] != 2){
				int lugar_atual = (i * M) + j;

				if((i + 1) < N && mapa[i + 1][j] != 2){
					grafo[lugar_atual][lugar_atual + M] = 1;
					grafo[lugar_atual + M][lugar_atual] = 1;
				}
				if((j + 1) < M && mapa[i][j + 1] != 2){
					grafo[lugar_atual][lugar_atual + 1] = 1;
					grafo[lugar_atual + 1][lugar_atual] = 1;
				}
			}
		}
	}

	/* Sabemos que L é a cidade aonde estamos logo inicializamos esta distância */
	vertices[L].distancia = 0;

	/* Agora iremos encontrar o melhor caminho de L até todos os nós adjacentes a L */
	dijkstra();

#ifdef DEBUG
	cout << endl;
	for(int i = 0; i < T; i++){
		for(int j = 0; j < T; j++){
			printf("%5d", grafo[i][j]);
		}
		cout << endl;
	}
	cout << endl << endl;

	for(int i = 0; i < T; i++){
		printf("%s%d: %d\n", ((find(saidas.begin(), saidas.end(), i) != saidas.end()) ? "*" : ""), i, vertices[i].distancia);
	}
	cout << endl;
#endif

	/* Após descobrir o melhor caminho a partir de L iremos varrer todos as saídas possíveis
	   e printar a distância para o melhor caminho */
	int menor_caminho = INFINITY_VALUE;
	for_each(it, saidas){
		Vertice *v = &vertices[*it];
		if(v->num != L && v->distancia <= menor_caminho){
			menor_caminho = v->distancia;
		}
	}

	/* Imprime o resultado */
	cout << menor_caminho << endl;

	return 0;
}<file_sep>/Lista_VIII/MINIMO.cpp
#include <bits/stdc++.h>
using namespace std;

/* Constantes do algoritmo */
#define MAX_NUM_VERTICES 120
#define BRANCO 0
#define CINZA  1
#define PRETO  2

/* For each */
#define for_each(member,container)  for(typeof(container.begin())   member  = container.begin(); \
                                                                    member != container.end();   \
                                                                    member ++ )


/* Verifica a existência */
#define is_none(var)        (var == NULL)
#define is_not_none(var)    (var != NULL)

/* Valor infinito */
#define INFINITY_VALUE 9999999
            
/* Indice nulo */
#define NULO -1

/* Ativar apenas durante o DEBUG */
//#define DEBUG

typedef struct VerticeStruct{
    int num;
    int cor;
    int d;
    int tempo_s;
    int tempo_f;
    struct VerticeStruct *anterior;
} Vertice;

int N, M;

#define MAX_NUM_VERTICES 120

int distk[MAX_NUM_VERTICES][MAX_NUM_VERTICES][MAX_NUM_VERTICES];

/* Floyd Warshall */
void FloydWarshall(){
    /* Executa o algoritmo de Floyd Warshall e computa as distancias */
    for(int i = 1; i <= N; i++){
        for(int j = 0; j < N; j++){
            for(int k = 0; k < N; k++){
                distk[i][j][k] = min(distk[i - 1][j][k], distk[i - 1][j][i - 1] + distk[i - 1][i - 1][k]);
            }
        }
    }
}

int main(){
	
	int inst = 1;

	while(true){

		/* Le os valores */
		if(scanf("%d %d", &N, &M) == EOF){
			break;
		}

		/* Inicializa os valores da distancia */
		for(int i = 0; i <= N; i++){
			for(int j = 0; j <= N; j++){
				for(int k = 0; k <= N; k++){
					if(j == k){
						distk[i][j][k] = 0;
					}
					else{
						distk[i][j][k] = INFINITY_VALUE;
					}
				}
			}
		}

		/* Le as arestas */
		for(int i = 0; i < M; i++){
			int u, v, w;
			cin >> u >> v >> w;
			distk[0][u - 1][v - 1] = min(distk[0][u - 1][v - 1], w);
		}

		/* Executa Floyd Warshal modificado para salvar as instancias k */
		FloydWarshall();

		int n_testes;
		cin >> n_testes;

		cout << "Instancia "<< inst << endl;

		/* Executa os testes */
		for(int i = 0; i < n_testes; i++){
			int u, v, t;
			cin >> u >> v >> t;
			if(distk[t][u - 1][v - 1] == INFINITY_VALUE){
				cout << "-1" << endl;
			}
			else{
				cout << distk[t][u - 1][v - 1] << endl;
			}
		}
		cout << endl;

		inst++;
	}

	return 0;
}<file_sep>/Lista_VI/ENERGIA.cpp
#include <iostream>
#include <cstdlib>
#include <list>

#define MAX_VERTICES 101

#define BRANCO 0
#define CINZA  1
#define PRETO  2

using namespace std;

typedef struct VerticeStruct{
    int cor;
    int tempo_d;
    int tempo_f;
    int num;
    struct VerticeStruct *pai;
} Vertice;

/* Tempo Global */
int tempo = 0;

/* Numero de Vertices */
int E;

/* Numero de visitas */
int comp_conexa;

/* Grafo & Vertices */

/* Matriz de Adjacência */
int grafo[MAX_VERTICES][MAX_VERTICES] = {{ 0 }};

/* Vertices */
Vertice vertices[MAX_VERTICES];

void DFS_VISIT(Vertice *u){
    int i;
    Vertice *v;  

    /* Atualiza os valores do tempo e do vertice */
    tempo += 1;
    u->tempo_d = tempo;
    u->cor = CINZA;

    /* Para cada vertice adjacente ao vertice atual */
    for(i = 1; i <= E; i++){
        /* Pula para o próxima adjacência possivel */
        if(grafo[u->num][i] == 0)
            continue;

        /* Vertice adjacente */
        v = &vertices[i];

        /* Se o vertice ainda não tiver sido visitado */
        if(v->cor == BRANCO){
            v->pai = u;
            DFS_VISIT(v);
        }
    }

    /* Finaliza a busca em profundidade */
    u->cor = PRETO;
    tempo += 1;
    u->tempo_f = tempo;
}

int main(){
    int i, j, k;
    int L, v1, v2;
    int test_num = 1;

    /* Executa enquanto E e L forem diferentes de 0 */
    do{
        /* Recupera E e L */
        cin >> E;
        cin >> L;

        /* Para a execução se E e L são iguais a 0*/
        if( E == 0 && L == 0 )
            break;

        /* Inicializa a matriz de adjacência e os vertices*/
        for(i = 1; i <= E; i++){
            for(j = 1; j <= E; j++){
                /* Matriz de adjacência */
                grafo[i][j] = 0;
            }
            
            /* Vertices */
            vertices[i].cor = BRANCO;
            vertices[i].pai = NULL;
            vertices[i].num = i;
        }

        /* Constrói a matriz de adjacências */
        for(i = 0; i < L; i++){
            /* Pega o vertice */
            cin >> v1;
            cin >> v2;

            /* Adiciona uma adjacência entre os dois vértices */
            grafo[v1][v2] += 1;
            grafo[v2][v1] += 1;
        }

        /* Executa uma busca em profundidade */
        /* Inicializa o tempo */
        tempo = 0;

        /* Inicializa as componentes conexas */
        comp_conexa = 0;

        /* Para cada vertice se o vertice ainda não tiver sido visitado executa uma busca em profundidade */
        for(int i = 1; i <= E; i++){
            if(vertices[i].cor == BRANCO){
                DFS_VISIT(&vertices[i]);
                comp_conexa += 1;
            }
        }

        /* Se este não for o primeiro teste imprima uma quebra de linha */
        if(test_num > 1){
            cout << endl;
        }

        /* Imprime o numero do teste */
        cout << "Teste " << test_num << endl;

        /* Se o número de visitas for igual ao número de vértices, temos ao menos um caminho entre todos eles */
        if(comp_conexa == 1){
            cout << "normal" << endl;
        }
        else {
            cout << "falha" << endl;
        }

        /* Incrementa o numero de execuções */
        test_num += 1;
    } while(E != 0 && L != 0);

    return EXIT_SUCCESS;
}
<file_sep>/Lista_II/BSEARCH1.cpp
#include <bits/stdc++.h>

#define MAX_SIZE_ARRAY 100001

using namespace std;

long long N;

long long vetor[MAX_SIZE_ARRAY] = { 0 };

long long binary_serch(long long valor){
	long long esquerda = 0;
	long long direita = N - 1;

	long long meio = 0;

	while(esquerda <= direita){
		meio =  esquerda + (direita - esquerda) / 2;
		if(vetor[meio] == valor){
			break;
		}
		else if(vetor[meio] > valor){
			direita = meio - 1;
		}
		else{
			esquerda = meio + 1;
		}
	}

	if(vetor[meio] == valor){
		for(int i = meio; i >= 0; i--){
			if(i == 0 && vetor[0] == valor){
				return 0;
			}
			else if(i > 0 && vetor[i - 1] != valor){
				return i;
			}
		}
	}

	return -1;
}

int main(){
	long long Q;
	
	scanf("%lld %lld", &N, &Q);

	for(long long i = 0; i < N; i++){
		scanf("%lld", &vetor[i]);
	}

	for(long long i = 0; i < Q; i++){
		long long valor;
		scanf("%lld", &valor);

		printf("%lld\n", binary_serch(valor));
	}

	return 0;
}<file_sep>/Lista_II/CARTEI14.cpp
#include <bits/stdc++.h>

#define MAX_SIZE_ARRAY 45001

using namespace std;

int N;

int vetor[MAX_SIZE_ARRAY] = { 0 };

int binary_serch(int esquerda, int direita, int valor){
	while(esquerda <= direita){
		int meio =  esquerda + (direita - esquerda) / 2;
		if(vetor[meio] == valor){
			return meio;
		}
		else if(vetor[meio] > valor){
			direita = meio - 1;
		}
		else{
			esquerda = meio + 1;
		}
	}

	return -1;
}

int main(){
	int M;

	scanf("%d %d", &N, &M);

	for(int i = 0; i < N; i++){
		scanf("%d", &vetor[i]);
	}

	int atual = 0;
	int soma = 0;

	for(int i = 0; i < M; i++){
		int valor;
		scanf("%d", &valor);

		int proxima_casa = binary_serch(0, N-1, valor);
		soma += proxima_casa > atual ? (proxima_casa - atual) : (atual - proxima_casa);
		//printf("%d - %d == %d\n", atual, proxima_casa, proxima_casa > atual ? (proxima_casa - atual) : (atual - proxima_casa));
		atual = proxima_casa;
	}

	printf("%d\n", soma);

	return 0;
}<file_sep>/README.md
# LABII-Listas
Listas de Laboratório de programação II - MATA 80 / UFBA
<file_sep>/Lista_VI/ORKUT.cpp
#include <iostream>
#include <list>
#include <queue>
#include <map>
#include <set>

/* Constantes do algoritmo */
#define MAX_NUM_VERTICES 300
#define BRANCO 0
#define CINZA  1
#define PRETO  2

/* For each */
#define for_each(member,container)  for(typeof(container.begin())   member  = container.begin(); \
                                                                    member != container.end();   \
                                                                    member ++ )

/* better find */
#define not_found_in(var)   var.end()

/* Max value between two vars */
#define max(var1, var2)     (var1 > var2 ? var1 : var2)

/* Verifica a existência */
#define is_none(var)        (var == NULL)
#define is_not_none(var)    (var != NULL)

/* Valor infinito */
#define INFINITY_VALUE std::numeric_limits<int>::max()

/* Ativar apenas durante o DEBUG */
//#define DEBUG

using namespace std;

typedef struct VerticeStruct{
    int num;
    int cor;
    int d;
    int tempo_s;
    int tempo_f;
    struct VerticeStruct *anterior;
} Vertice;

/* Estrutura do grafo - arestas e vertices */
int saida[MAX_NUM_VERTICES];
int dependecia[MAX_NUM_VERTICES];
list<int> grafo[MAX_NUM_VERTICES];
Vertice vertices[MAX_NUM_VERTICES];

/* Tempo Global */
int tempo;

/* Variaveis do programa */
int N, M;

/* Mapeamento dos vertices com string */
map<string, int> nome_vertices;
map<int, string> id_vertices;

/* Verifica a existência de dependecia */
#define nao_tem_dependecia(var) (dependecia[var] == 0)

/* Ordena tarefas */
int OrdenacaoTopologica(){
    /* Criamos uma fila de prioridades */
    set<int> Q;

    /* Items ordenados */
    int qtd_itens_ordenados = 0;

    /* Enfileiramos todos os valores que não tem precedência */
    for(int i = 1; i <= N; i++){
        if(nao_tem_dependecia(i)){
            Q.insert(i);
        }
    }

    /* Enquanto a fila não estiver vazia */
    while(!Q.empty()){
        Vertice *u = &vertices[*(Q.begin())];
        Q.erase(Q.begin());

        #ifdef DEBUG
        cout << u->num <<  " ";
        #endif

        /* Para cada vértice adjacente a u */
        for_each(it, grafo[u->num]){
            Vertice *v = &vertices[*it];

            dependecia[v->num] -= 1;
            if(nao_tem_dependecia(v->num)){
                Q.insert(v->num);
            }
        }
        
        /* Após modificarmos a precedência dos nós adjacentes e empilharmos os que não tinham dependencia */
        saida[qtd_itens_ordenados] = u->num;
        qtd_itens_ordenados += 1;
    }

    return qtd_itens_ordenados;
}

int main(){
    int z = 1;


    do{
        /* Lê as entradas */
        cin >> N;

        /* Se condição de parada da aplicação for atingida */
        if(N == 0)
            break;

        /* Inicalização do grafo */
        nome_vertices.clear();
        id_vertices.clear();
        tempo = 0;
        for(int i = 1; i <= N; i++){
            /* Vertices */
            vertices[i].cor = BRANCO;
            vertices[i].num = i;
            vertices[i].anterior = NULL;

            /* Dependencias */
            dependecia[i] = 0;

            /* Resposta */
            saida[i] = 0;

            /* Valor de cada vertice */
            /* Inicializa a chave se a mesma for nova na tabela de simbolos */
            string amigo;
            cin >> amigo;
            nome_vertices[amigo] = i;
            id_vertices[i] = amigo;

            #ifdef DEBUG
            cout << ">>> " << amigo << " ID " << nome_vertices[amigo] << endl;
            #endif

            /* Arestas */
            grafo[i].clear();
        }

        /* Lê as arestas */
        for(int i = 0; i < N; i++){
            string amigo;
            int n_amigos;

            /* Pega o nome de cada amigo e a lista de amigos desse amigo */
            cin >> amigo;
            cin >> n_amigos;

            /* Associa o valor da string a um numero inteiro qualquer */
            int id_amigo = nome_vertices[amigo];
            
            #ifdef DEBUG
            cout << "amigo = " << amigo << endl;
            cout << "id_amigo = " << id_amigo << " id_preador = " << id_predador << endl;
            #endif

            /* Como "ser amigo" é direcional */
            for(int j = 0; j < n_amigos; j++){
                string amigo_do_amigo;
                cin >> amigo_do_amigo;
                int id_amigo_do_amigo = nome_vertices[amigo_do_amigo];
                grafo[id_amigo_do_amigo].push_back(id_amigo);
                dependecia[id_amigo] += 1;
            }
        }

        /* Tenta ordenar as tarefas */
        int qtd_tarefas_ordenadas = OrdenacaoTopologica();

        if(z > 1){
            cout << '\n';
        }

        cout << "Teste " << z << '\n';

        /* Se a qtd de amigos ordenadas for igual ao total de nós imprimiremos a sequencia */
        if(qtd_tarefas_ordenadas == N){
            for(int i = 0; i < N; i++){
                if(i > 0){
                    cout << ' ';
                }
                cout << id_vertices[saida[i]];
            }
        }
        else{
            /* Caso contrário imprimimos que não é possível */
            cout << "impossivel";
        }
        cout << '\n';

        z += 1;

    }while(true);

    return 0;
}
<file_sep>/Lista_III/EELCS.cpp
#include <bits/stdc++.h>

#define MAX_STRING_SIZE 5001

#define max(A, B) (A > B ? A : B)

using namespace std;

char str1[MAX_STRING_SIZE];
char str2[MAX_STRING_SIZE];

int lcs_matrix_1[MAX_STRING_SIZE + 1] = { 0 };
int lcs_matrix_2[MAX_STRING_SIZE + 1] = { 0 };
int *lcs_previous_matrix;
int *lcs_actual_matrix;

int main(){
	int lcs;

	scanf("%s%*c", str1);
	scanf("%s%*c", str2);
	int size_str1 = strlen(str1);
	int size_str2 = strlen(str2);

//	for(int i = 0, j = size_str1 - 1; i < size_str1; i++, j--){
//		str2[j] = str1[i];
//	}

	int z;

	for(int i = 1; i <= size_str1; i++){
		if(i % 2){
			lcs_previous_matrix = lcs_matrix_1;
			lcs_actual_matrix = lcs_matrix_2;
		}
		else{
			lcs_previous_matrix = lcs_matrix_2;
			lcs_actual_matrix = lcs_matrix_1;	
		}

		for(int j = 1; j <= size_str2; j++){
			if(str1[i - 1] == str2[j - 1]){
				lcs_actual_matrix[j] = lcs_previous_matrix[j - 1] + 1;
			}
			else{
				lcs_actual_matrix[j] = max(	lcs_previous_matrix[j],
											lcs_actual_matrix[j - 1]);
			}
		}
	}

	lcs = lcs_actual_matrix[size_str2];

	printf("%d\n", lcs);

	return EXIT_SUCCESS;
}<file_sep>/Lista_IX/MANUT.cpp
#include <iostream>
#include <list>
#include <queue>
#include <limits>

/* Constantes do algoritmo */
#define MAX_NUM_VERTICES 450
#define BRANCO 0
#define CINZA  1
#define PRETO  2

/* For each */
#define for_each(member,container)  for(typeof(container.begin())   member  = container.begin(); \
                                                                    member != container.end();   \
                                                                    member ++ )

/* better find */
#define not_found_in(var)   var.end()

/* Max value between two vars */
#define max_2(var1, var2)   (var1 > var2 ? var1 : var2)

/* Min value between two vars */
#define min_2(var1, var2)   (var1 < var2 ? var1 : var2)

/* Verifica a existência */
#define is_none(var)        (var == NULL)
#define is_not_none(var)    (var != NULL)

/* Valor infinito */
#define INFINITY_VALUE std::numeric_limits<int>::max()

/* Ativar apenas durante o DEBUG */
//#define DEBUG

using namespace std;

typedef struct VerticeStruct{
    int num;
    int cor;
    int d;
    int low;
    int tempo_f;
    bool corte;
    struct VerticeStruct *anterior;
} Vertice;

/* Estrutura do grafo - arestas e vertices */
list<int> grafo[MAX_NUM_VERTICES];
Vertice vertices[MAX_NUM_VERTICES];

/* Tempo Global */
int tempo;

/* Variaveis do programa */
int N, M;

void printaVazio(int qtd){
    for(int i = 0; i < qtd; i++){
        cout << " ";
    }
}

int root;
int root_n;

/* Visita os nós adjancentes, utilizando busca em profundidade */
void DFS_visit(Vertice *u){
    /* Atualiza o valor do tempo e indica que está sendo visitado */
    u->d = tempo;
    u->low = tempo;
    tempo += 1;
    u->cor = CINZA;

    /* Para cada vértice adjacente a u */
    for_each(it, grafo[u->num]){
        Vertice *v = &vertices[*it];

        /* Caso ele seja branco */
        if(v->cor == BRANCO){
            /* Se for nó de raiz */
            if(u->num == root){
                root_n += 1;
            }

            v->anterior = u;
            DFS_visit(v);
            
            /* Verifica se temos uma aresta de corte e indica que são vertices de corte */
            if(v->low >= u->d){
                u->corte = true;
                #ifdef DEBUG
                cout << "ACHOU UM PONTO DE ARTICULACAO " << u->num << endl;
                #endif 
            }

            u->low = min_2(u->low, v->low);
        }
        else if(u->anterior != v){
            u->low = min(u->low, v->d);
        }
    }

    /* Finaliza a busca em profundidade do nó atual */
    u->cor = PRETO;
}

int main(){
    int z = 1;

    do{
        /* Lê as entradas */
        cin >> N;
        cin >> M;

        /* Se condição de parada da aplicação for atingida */
        if(N == 0 && M == 0)
            break;

        /* Inicalização do grafo */
        tempo = 0;
        root = 1;
        root_n = 0;
        for(int i = 1; i <= N; i++){
            /* Vertices */
            vertices[i].cor = BRANCO;
            vertices[i].num = i;
            vertices[i].low = 0;
            vertices[i].d = 0;
            vertices[i].anterior = NULL;
            vertices[i].corte = false;

            /* Arestas */
            grafo[i].clear();
        }

        /* Lê as arestas */
        for(int i = 0; i < M; i++){
            int X;
            int Y;

            cin >> X;
            cin >> Y;

            /* Adicionamos a ida e a volta para o vértice adjacente já que temos um grafo não direcionado */
            grafo[X].push_back(Y);
            grafo[Y].push_back(X);
        }

        /* Executa uma DFS */
        /* Iremos contar o tamanho de cada ciclo e armazenar o valor do ciclo maior */
        for(int i = 1; i <= N; i++){
            if(vertices[i].cor == BRANCO){
                DFS_visit(&vertices[i]);
            }
        }

        /* Para o no raiz ser nó de corte ele precisa ter mais de 1 filho */
        vertices[root].corte = (root_n > 1);

        if(z > 1){
            cout << '\n';
        }

        /* Imprime os vertices de corte */
        cout << "Teste " << z << '\n';
        int k = 0;
        for(int u = 1; u <= N; u++){
            Vertice *v = &vertices[u];

            if(v->corte){
                if(k > 0){
                    cout << ' ';
                }
                k += 1;
                cout << v->num;
            }
        }
        if(k == 0){
            cout << "nenhum";
        }
        cout << '\n';

        /* Contador de número de testes */
        z += 1;

    }while(true);

    return 0;
}
<file_sep>/Lista_VI/IREVIR.cpp
#include <iostream>
#include <stack>
#include <list>

#define MAX_NUM_VERTICES 2200
#define BRANCO 0
#define CINZA  1
#define PRETO  2

/* For each */
#define for_each(member,container) 	for(typeof(container.begin())   member  = container.begin();  \
									                                member != container.end();    \
                                                                    member ++ )

// APENAS PARA PROPOSITOS DE DEBUG
//#define DEBUG

using namespace std;

typedef struct VerticeStruct{
    int num;
    int cor;
    int tempo_f;
    int tempo_s; // Ou d
    struct VerticeStruct *anterior;
} Vertice;

list<int> grafo[MAX_NUM_VERTICES];
Vertice vertices[MAX_NUM_VERTICES];

/* Grafo transposto */
list<int> gr[MAX_NUM_VERTICES];

/* Tempo Global */
int tempo;

/* Variaveis do programa */
int N, M;

/* Pilha com a ordem de visitação */
stack<int> Q;

/* Contador de SCC */
int scc_count;

/* Visita os nós adjancentes, utilizando busca em profundidade */
void DFS_visit(Vertice V[MAX_NUM_VERTICES], Vertice *u){
    /* Atualiza o valor do tempo e indica que está sendo visitado */
    tempo += 1;
    u->tempo_s = tempo;
    u->cor = CINZA;

    #ifdef DEBUG
    cout << u->num << " ";
    #endif

    /* Para cada vértice adjacente a u */
    for_each(it, gr[u->num]){
        Vertice *v = &V[*it];

        /* Se o vertice ainda não tiver sido visitado */
        if(v->cor == BRANCO){
            v->anterior = u;
            DFS_visit(V, v);
        }
    }

    /* Finaliza a busca em profundidade do nó atual */
    u->cor = PRETO;
    tempo += 1;
    u->tempo_f = tempo;
}

/* Visita os nós adjancentes, utilizando busca em profundidade */
void DFS_visit_ordem(Vertice *u){
    /* Atualiza o valor do tempo e indica que está sendo visitado */
    tempo += 1;
    u->tempo_s = tempo;
    u->cor = CINZA;

    /* Para cada vértice adjacente a u */
    for_each(it, grafo[u->num]){
        Vertice *v = &vertices[*it];

        /* Se o vertice ainda não tiver sido visitado */
        if(v->cor == BRANCO){
            v->anterior = u;
            DFS_visit_ordem(v);
        }
    }

    /* Finaliza a busca em profundidade do nó atual */
    u->cor = PRETO;
    tempo += 1;
    u->tempo_f = tempo;

    /* Todos os nós que são acessiveis por u serão processados nesse momento */
    Q.push(u->num);
}

/* Computa os SCC ou seja os Strongly Conected Components do grafo global */
void SCC_kosaraju(){
    /* Toda vez que executarmos um DFS teremos que zerar o contador */
    tempo = 0;

    /* Executa uma DFS */
    /* Para cada vertice se o vertice ainda não tiver sido visitado executa uma
    busca em profundidade e computa seu tempo final de execução */
    for(int i = 1; i <= N; i++){
        if(vertices[i].cor == BRANCO){
            DFS_visit_ordem(&vertices[i]);
        }
    }

    /* Cria um grafo transposto ou reverso */
    Vertice V[MAX_NUM_VERTICES];

    /* Inicializamos os vertices V de gr */
    for(int i = 1; i <= N; i++){
        V[i].cor = BRANCO;
        V[i].anterior = NULL;
        V[i].num = i;
    }

    /* Enquanto Q não estiver vazio */
    tempo = 0;
    while(!Q.empty()){
        Vertice *u = &V[Q.top()];
        Q.pop();

        /* Se o vertice não tiver sido visitado ainda */
        if(u->cor == BRANCO){
            DFS_visit(V, u);

            /* Incrementa o numero de SCC */
            scc_count += 1;

            #ifdef DEBUG
            cout << endl;
            #endif
        }
    }
}

int main(){

    do{
        /* Lê as entradas */
        cin >> N;
        cin >> M;

        /* Se condição de parada da aplicação for atingida */
        if(N == 0 && M == 0)
        	break;

        /* Inicalização do grafo */
		scc_count = 0;
        for(int i = 1; i <= N; i++){
            /* Vertices */
            vertices[i].cor = BRANCO;
            vertices[i].anterior = NULL;
            vertices[i].num = i;

            /* Arestas */
			gr[i].clear();
			grafo[i].clear();
        }

        /* Lê as arestas */
        for(int i = 0; i < M; i++){
            int V, W, P;

            cin >> V;
            cin >> W;
            cin >> P;

            /* Se o nó tiver apenas o caminho de ida */
            grafo[V].push_back(W);

            /* Matriz transposta */
            gr[W].push_back(V);

            /* Caso o mesmo tenha também a volta -- grafo direcionado */
            if(P == 2){
                grafo[W].push_back(V);
            	gr[V].push_back(W);
            }
        }

        /* Executamos uma */
        SCC_kosaraju();

        /* Se tivermos apenas uma SCC então nosso grafo é fortemente conectado ou SCC */
        cout << (scc_count == 1 ? "1" : "0") << endl;

    	#ifdef DEBUG
        cout << "SCC = " << scc_count << endl;
        #endif

    }while(N != 0 && M != 0);

    return 0;
}
<file_sep>/Lista_VII/REDOTICA.cpp
#include <iostream>
#include <queue>
#include <list>
#include <limits>
#include <set>

#define MAX_NUM_VERTICES 101
#define BRANCO 0
#define CINZA  1
#define PRETO  2

/* For each */
#define for_each(member,container)  for(typeof(container.begin())   member  = container.begin(); \
                                                                    member != container.end();   \
                                                                    member ++ )

/* better find */
#define not_found_in(var)   var.end()

/* Max value between two vars */
#define max_2(var1, var2)     (var1 > var2 ? var1 : var2)
#define min_2(var1, var2)     (var1 < var2 ? var1 : var2)

/* Verifica a existência */
#define is_none(var)        (var == NULL)
#define is_not_none(var)    (var != NULL)

/* Valor infinito */
#define INFINITY_VALUE std::numeric_limits<int>::max()
            
/* Indice nulo */
#define NULO -1

// APENAS PARA PROPOSITOS DE DEBUG
//#define DEBUG

using namespace std;

typedef struct VerticeStruct{
    int num;
    int cor;
    struct VerticeStruct *anterior;
} Vertice;

/* Estrutura do grafo - arestas e vertices */
int grafo[MAX_NUM_VERTICES][MAX_NUM_VERTICES];
Vertice vertices[MAX_NUM_VERTICES];

/* Matrizes do Floyd Warshall */
int dist[MAX_NUM_VERTICES][MAX_NUM_VERTICES] = {{ 0 }};
int custo[MAX_NUM_VERTICES][MAX_NUM_VERTICES] = {{ 0 }};
int parente[MAX_NUM_VERTICES][MAX_NUM_VERTICES] = {{ 0 }};
int pai[MAX_NUM_VERTICES] = { 0 };

/* Variaveis do programa */
int N, M;

/* Floyd Warshall */
void FloydWarshall(){
    /* Executa o algoritmo de Floyd Warshall e computa as distancias */
    for(int k = 1; k <= N; k++){
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                if( dist[i][k] != INFINITY_VALUE &&
                    dist[k][j] != INFINITY_VALUE &&
                    (dist[i][k] + dist[k][j] < dist[i][j])){
                    dist[i][j] = dist[i][k] + dist[k][j];
                    parente[i][j] = k;
                }
            }
        }
    }

    #ifdef DEBUG
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            if (dist[i][j] == INFINITY_VALUE){
                printf("%7s", "INF");
            }
            else{
                printf ("%7d", dist[i][j]);
            }
        }
        cout << '\n';
    }
    cout << '\n';
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            if (parente[i][j] == NULO){
                printf("%7s", "NIL");
            }
            else{
                printf ("%7d", parente[i][j]);
            }
        }
        cout << '\n';
    }
    cout << '\n';
    #endif
}

struct compare
{
    bool operator ()(const pair<pair<int, int>, int>&i, const pair<pair<int, int>, int>&j){
        return i.second <= j.second;
    };
};


struct compare2
{
    bool operator ()(const pair<pair<int, int>, int>&i, const pair<pair<int, int>, int>&j){
        if(i.first.first != j.first.first)
            return (i.first.first < j.first.first);
        return (i.first.second < j.first.second);
    };
};

/* Distância de u a v */
#define w(u, v) (dist[u][v])

/* Define a união dos parentes */
#define union(u, v) pai[u] = pai[v]

/* Procura o parente de um dado vértice */
int find_set(int v){
    if(v != pai[v])
        pai[v] = find_set(pai[v]);
    return pai[v];
}

/* Arvore geradora minima do Kruskal */
set<pair<pair<int,int>,int>, compare2> A;

int Kruskal(){
    /* Pair de cordenadas e custo modelo: <<u,v>, custo>, e ordenamos o mesmo pelo custo */
    set<pair<pair<int,int>,int>, compare> Q;

    /* Insere no set a lista de pares e custo */
    for(int u = 1; u <= N; u++){
        for(int v = 1; v <= N; v++){
            if(grafo[u][v] != 0){
                Q.insert(make_pair(make_pair(u, v), w(u,v)));
#ifdef DEBUG
                cout << "u -- " << u << " | v -- " << v << " | w -- " << w(u,v) << endl;
#endif                
            }
        }
    }

#ifdef DEBUG
    /* Imprime todos os nós - deve estar ordenado pelo peso */
    cout << "Todas arestas" << endl;
    for_each(it, Q){
        int u = it->first.first;
        int v = it->first.second;
        int w = it->second;
        cout << "u " << u << " v " << v << " w " << w << endl;   
    }
#endif

    /* While n of nodes is different of 0 */
    int n_nodes = 0;
    int soma = 0;
    for_each(it, Q){
        /* Pega os pares u e v da lista */
        int u = it->first.first;
        int v = it->first.second;

        /* Executa o find_set para os nós u e v */
        int find_set_u = find_set(u);
        int find_set_v = find_set(v);
        
        /* Se o pai de u for diferente do pai de v */
        if(find_set_u != find_set_v){
            /* Inserimos os valores de u, v e w ordenado */
            int u_aux = it->first.first;
            int v_aux = it->first.second;
            int w_aux = it->second;

            /* Verificamos se u < v */
            if(u_aux < v_aux){
                A.insert(make_pair(make_pair(u_aux, v_aux), w_aux));
            }
            else{
                A.insert(make_pair(make_pair(v_aux, u_aux), w_aux));
            }

            /* Adiciona o custo final e une os elementos */
            soma += it->second;
            union(find_set_u, find_set_v);
        }

        /* Se já temos nossa arvore geradora minima paramos a execução */
        if(A.size() == (N - 1)){
            break;
        }
    }

#ifdef DEBUG
    /* Imprime todos os nós da nossa arvore geradora minima */
    cout << "Arvore geradora minima" << endl;
    for_each(it, A){
        int u = it->first.first;
        int v = it->first.second;
        int w = it->second;
        cout << "u " << u << " v " << v << " w " << w << endl;   
    }
#endif

    return soma;
}

int main(){
    int U, V, C;
    int z = 1;

    do{
        /* Lê as entradas */
        cin >> N;
        cin >> M;

        if(N == 0 && M == 0)
            break;

        /* Inicalização do grafo */
        A.clear();
        for(int i = 1; i <= N; i++){
            /* Vertices */
            vertices[i].cor = BRANCO;
            vertices[i].anterior = NULL;
            vertices[i].num = i;

            /* Arestas & Distâncias & Caminho */
            for(int j = 1; j <= N; j++){
                dist[i][j] = INFINITY_VALUE;
                grafo[i][j] = 0;
                parente[i][j] = NULO;
            }

            /* Distâncias & Parentes na Diagonal */
            dist[i][i] = 0;
            parente[i][i] = i;
            pai[i] = i;
        }

        /* Lê as arestas */
        for(int i = 0; i < M; i++){
            /* Pega os valores de A e B*/
            cin >> U;
            cin >> V;
            cin >> C;

            /* Como temos um grafo não direcionado os dois caminhos são válidos */
            grafo[U][V] += 1;
            grafo[V][U] += 1;

            /* Custo de U a V */
            dist[U][V] = C;
            dist[V][U] = C;

            /* Menor caminho de U a V */
            parente[U][V] = U;
            parente[V][U] = V;
        }

        if(z > 1){
            cout << endl;
        }

        /* Iremos construir uma arvore geradora minima usando Kruskal, e
           retornar o custo do menor caminho entre todos os nós */
        int retorno = Kruskal();

        cout << "Teste " << z << endl;
        for_each(it, A){
            int u = it->first.first;
            int v = it->first.second;
            if(u < v){
                cout << u << " " << v << endl;   
            }
            else{
                cout << v << " " << u << endl;   
            }
        }
        
        /* Incrementamos o numero de testes executados */
        z += 1;
    } while(true);

    return 0;
}
<file_sep>/Lista_VI/NATUREZA.cpp
#include <iostream>
#include <list>
#include <queue>
#include <map>

// Essa eu ja tinha feito semestre passado também

/* Constantes do algoritmo */
#define MAX_NUM_VERTICES 6002
#define BRANCO 0
#define CINZA  1
#define PRETO  2

/* For each */
#define for_each(member,container)  for(typeof(container.begin())   member  = container.begin(); \
                                                                    member != container.end();   \
                                                                    member ++ )

/* better find */
#define not_found_in(var)   var.end()

/* Max value between two vars */
#define max(var1, var2)     (var1 > var2 ? var1 : var2)

/* Verifica a existência */
#define is_none(var)        (var == NULL)
#define is_not_none(var)    (var != NULL)

/* Valor infinito */
#define INFINITY_VALUE std::numeric_limits<int>::max()

/* Ativar apenas durante o DEBUG */
//#define DEBUG

using namespace std;

typedef struct VerticeStruct{
    int num;
    int cor;
    int d;
    int tempo_s;
    int tempo_f;
    struct VerticeStruct *anterior;
} Vertice;

/* Estrutura do grafo - arestas e vertices */
list<int> grafo[MAX_NUM_VERTICES];
Vertice vertices[MAX_NUM_VERTICES];

/* Tempo Global */
int tempo;

/* Variaveis do programa */
int C, R;

/* Mapeamento dos vertices com string */
map<string, int> nome_vertices;

void printaVazio(int qtd){
    for(int i = 0; i < qtd; i++){
        cout << " ";
    }
}

/* Visita os nós adjacentes, utilizando busca em largura */
int BFS(Vertice *s){
    /* Começa a consulta do primeiro valor */
    //Vertice *s = &vertices[1];

    /* Inicializamos o nó em questão */
    s->cor = CINZA;
    s->d = 0;
    s->anterior = NULL;

    /* Tamanho do ciclo */
    int tamanho_ciclo = 1;

    /* Criamos uma fila de prioridades */
    queue<int> Q;

    /* Enfileiramos o primeiro valor */
    Q.push(s->num);

    /* Enquanto a fila não estiver vazia */
    while(!Q.empty()){
        Vertice *u = &vertices[Q.front()];
        Q.pop();

        #ifdef DEBUG
        cout << u->num <<  " ";
        #endif

        /* Para cada vértice adjacente a u */
        for_each(it, grafo[u->num]){
            Vertice *v = &vertices[*it];

            /* Se o vertice não tiiver sido visitado, marca ele como visitado, enfileira e modifica */
            if(v->cor == BRANCO){
                /* Setamos os valores do vértice adjacente */
                v->anterior = u;
                v->cor = CINZA;
                v->d = u->d + 1;
                
                /* Empilhamos o número do vértice adjacente atual */
                Q.push(v->num);

                /* Incrementamos em 1 o tamanho do ciclo */
                tamanho_ciclo += 1;
            }
        }
        
        /* Finaliza a consulta */
        u->cor = PRETO;
    }

    
    #ifdef DEBUG
    cout << endl;
    #endif

    return tamanho_ciclo;
}

/* Visita os nós adjancentes, utilizando busca em profundidade */
int DFS_visit(Vertice *u, int grau){
    /* Atualiza o valor do tempo e indica que está sendo visitado */
    tempo += 1;
    u->tempo_s = tempo;
    u->cor = CINZA;

    /* Quantidade de nos */
    int quantidade_ciclos = 1;

    #ifdef DEBUG
    printaVazio(grau);
    cout << " -- Inicio -- " << endl;
    #endif

    /* Para cada vértice adjacente a u */
    for_each(it, grafo[u->num]){
        Vertice *v = &vertices[*it];

        /* Caso ele seja branco */
        if(v->cor == BRANCO){
            v->anterior = u;
            quantidade_ciclos += DFS_visit(v, grau + 3);
            
            #ifdef DEBUG
            printaVazio(grau);
            cout << " -- Encontrado Ciclo -- > X = " << quantidade_ciclos << endl;
            #endif
        }
    }

    #ifdef DEBUG
    printaVazio(grau);
    cout << " > " << quantidade_ciclos << endl;
    printaVazio(grau);
    cout << " -- Fim -- " << endl;
    #endif

    /* Finaliza a busca em profundidade do nó atual */
    u->cor = PRETO;
    tempo += 1;
    u->tempo_f = tempo;

    /* Retorna o contador de ciclo */
    return quantidade_ciclos;
}

int main(){

    do{
        /* Lê as entradas */
        cin >> C;
        cin >> R;

        /* Se condição de parada da aplicação for atingida */
        if(C == 0)
            break;

        /* Inicalização do grafo */
        nome_vertices.clear();
        tempo = 0;
        for(int i = 1; i <= C; i++){
            /* Vertices */
            vertices[i].cor = BRANCO;
            vertices[i].num = i;
            vertices[i].anterior = NULL;

            /* Valor de cada vertice */
            /* Inicializa a chave se a mesma for nova na tabela de simbolos */
            string alimento_ou_preador;
            cin >> alimento_ou_preador;
            //nome_vertices.insert(make_pair(alimento_ou_preador, i));
            nome_vertices[alimento_ou_preador] = i;

            #ifdef DEBUG
            cout << ">>> " << alimento_ou_preador << " ID " << nome_vertices[alimento_ou_preador] << endl;
            #endif

            /* Arestas */
            grafo[i].clear();
        }

        /* Lê as arestas */
        for(int i = 0; i < R; i++){
            string alimento, preador;

            /* Pega o nome de cada alimento e seu respectivo predador */
            cin >> alimento;
            cin >> preador;

            /* Associa o valor da string a um numero inteiro qualquer */
            int id_alimento = nome_vertices[alimento];
            int id_predador = nome_vertices[preador];

            #ifdef DEBUG
            cout << "alimento = " << alimento << " preador = " << preador << endl;
            cout << "id_alimento = " << id_alimento << " id_preador = " << id_predador << endl;
            #endif

            /* Como alimento e preador estão na mesma cadeia, temos tanto a ida como a volta */
            grafo[id_predador].push_back(id_alimento);
            grafo[id_alimento].push_back(id_predador);
        }

        /* Maior cadeia alimentar */
        int maior_ciclo = 0;

        /* Executa uma DFS */
        /* Iremos contar o tamanho de cada ciclo e armazenar o valor do ciclo maior */
        for(int i = 1; i <= C; i++){
            if(vertices[i].cor == BRANCO){
                //int qtd_ciclos_atual = DFS_visit(&vertices[i], 0);
                int qtd_ciclos_atual = BFS(&vertices[i]);
                maior_ciclo = max(maior_ciclo, qtd_ciclos_atual);
            }
        }

        /* Imprime o maior ciclo */
        cout << maior_ciclo << endl;

    }while(C != 0);

    return 0;
}
<file_sep>/Lista_VIII/PONTES09.cpp
#include <bits/stdc++.h>

#define INFINITY_VALUE std::numeric_limits<int>::max()
#define MAX_NUM_VERTICES 1002
#define UNDEFINED_VERTICE -1

/* Distância de u a v */
#define distancia(u,v) v

using namespace std;

typedef struct VerticeStruct{
	int num;
	int distancia;
	int anterior;
} Vertice;

/* For each */
#define for_each(member,container) 	for(typeof(container.begin())   member  = container.begin();  \
									                                member != container.end();    \
                                                                    member ++ )

#define NAO_VISITADO 0
#define VISITANDO 1
#define VISITADO 2

Vertice vertices[MAX_NUM_VERTICES];
vector<pair<int, int> > grafo[MAX_NUM_VERTICES];
vector<int> menor_caminho;

int N, M, L = 0;

void dijkstra(){
	/* Criamos uma fila de prioridades */
	priority_queue<pair<int, int> > Q;

	/* Adicionamos o vértice de origem */
	Q.push(make_pair(0, L));

	/* Enquanto nossa fila não estiver vazia */
	while(!Q.empty()){
		/* Extraimos o menor vertice de nossa fila */
		Vertice *u = &vertices[Q.top().second];
		Q.pop();

		/* Para cada vizinho v de u */
		for(int vi = 0; vi < grafo[u->num].size(); vi++){
			/* Vertice V */
			int v = grafo[u->num][vi].first; 
			int v_peso = grafo[u->num][vi].second;

			/* Some a distancia de u com a distancia de u a v
			como temos que a distância é fixa, ela é igual a 1 */
			int alternativa = u->distancia + v_peso;
			/* Se o novo caminho for o melhor caminho armazene ele */
			if (alternativa < vertices[v].distancia){
				vertices[v].distancia = alternativa;
				vertices[v].anterior = u->num;
				Q.push(make_pair(vertices[v].distancia, vertices[v].num));	
			}
		}
	}
}

int main(){

	cin >> N >> M;

	for(int i = 0; i <= N + 1; i++){
		grafo[i].clear();
		vertices[i].num = i;
		vertices[i].distancia = INFINITY_VALUE;
		vertices[i].anterior = UNDEFINED_VERTICE;
	}

	for(int i = 0; i < M; i++){
		int S, T, B;

		cin >> S >> T >> B;

		grafo[S].push_back(make_pair(T, B));
		grafo[T].push_back(make_pair(S, B));
	}

	/* Destino a ser alcançado */
	int destino = N + 1;

	vertices[0].distancia = 0;

	dijkstra();

	cout << vertices[destino].distancia << endl;

	return 0;
}<file_sep>/Lista_II/PROIBIDO.cpp
#include <bits/stdc++.h>

#define MAX_SIZE_ARRAY 140001

using namespace std;

int N;

int vetor[MAX_SIZE_ARRAY] = { 0 };

int cmpfunc (const void * a, const void * b)
{
   return (*(int*)a - *(int*)b);
}


int binary_serch(int valor){
	int esquerda = 0;
	int direita = N - 1;

	while(esquerda <= direita){
		int meio =  esquerda + (direita - esquerda) / 2;
		if(vetor[meio] == valor){
			return meio;
		}
		else if(vetor[meio] > valor){
			direita = meio - 1;
		}
		else{
			esquerda = meio + 1;
		}
	}

	return -1;
}

int main(){
	scanf("%d", &N);

	for(int i = 0; i < N; i++){
		scanf("%d", &vetor[i]);
	}

	qsort(vetor, N, sizeof(int), cmpfunc);

	while(true){		
		int valor;
		if(scanf("%d", &valor) == EOF) break;

		printf("%s\n", binary_serch(valor) != -1 ? "sim" : "nao");
	}

	return 0;
}<file_sep>/Lista_VI/DENGUE.cpp
#include <iostream>
#include <cstdio>
#include <limits>

/* Constantes do algoritmo */
#define MAX_NUM_VERTICES 120
#define BRANCO 0
#define CINZA  1
#define PRETO  2

/* For each */
#define for_each(member,container)  for(typeof(container.begin())   member  = container.begin(); \
                                                                    member != container.end();   \
                                                                    member ++ )

/* better find */
#define not_found_in(var)   var.end()

/* Max value between two vars */
#define max_2(var1, var2)     (var1 > var2 ? var1 : var2)
#define min_2(var1, var2)     (var1 < var2 ? var1 : var2)

/* Verifica a existência */
#define is_none(var)        (var == NULL)
#define is_not_none(var)    (var != NULL)

/* Valor infinito */
#define INFINITY_VALUE std::numeric_limits<int>::max()
            
/* Indice nulo */
#define NULO -1

/* Ativar apenas durante o DEBUG */
//#define DEBUG

using namespace std;

typedef struct VerticeStruct{
    int num;
    int cor;
    int d;
    int tempo_s;
    int tempo_f;
    struct VerticeStruct *anterior;
} Vertice;

/* Estrutura do grafo - arestas e vertices */
int grafo[MAX_NUM_VERTICES][MAX_NUM_VERTICES] = {{ 0 }};
int dist[MAX_NUM_VERTICES][MAX_NUM_VERTICES] = {{ 0 }};
int parente[MAX_NUM_VERTICES][MAX_NUM_VERTICES] = {{ 0 }};
Vertice vertices[MAX_NUM_VERTICES];

/* Tempo Global */
int tempo;

/* Variaveis do programa */
int N;

/* Floyd Warshall */
int FloydWarshall(){
    /* Executa o algoritmo de Floyd Warshall e computa as distancias */
    for(int k = 1; k <= N; k++){
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                if( dist[i][k] != INFINITY_VALUE &&
                    dist[k][j] != INFINITY_VALUE &&
                    (dist[i][k] + dist[k][j] < dist[i][j])){
                    dist[i][j] = dist[i][k] + dist[k][j];
                    parente[i][j] = k;
                }
            }
        }
    }

    /* Inicia a menor distância entre todos os nós como sendo o infinito */
    int menor_distancia = INFINITY_VALUE;
    int vertice_menor_distancia = 1;

    for(int u = 1; u <= N; u++){
        int distancia = 0;
        for(int v = 1; v <= N; v++){
            distancia = max_2(distancia, dist[u][v]);
        }
        if(distancia < menor_distancia){
            menor_distancia = distancia;
            vertice_menor_distancia = u;
        }
    }
    #ifdef DEBUG
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            if (dist[i][j] == INFINITY_VALUE){
                printf("%7s", "INF");
            }
            else{
                printf ("%7d", dist[i][j]);
            }
        }
        cout << '\n';
    }
    cout << '\n';
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            if (parente[i][j] == NULO){
                printf("%7s", "NIL");
            }
            else{
                printf ("%7d", parente[i][j]);
            }
        }
        cout << '\n';
    }
    cout << '\n';
    #endif

    return vertice_menor_distancia;
}


int main(){
    int z = 1;

    /* CIN Improvements */
    //ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    do{
        /* Lê as entradas */
        cin >> N;

        /* Se condição de parada da aplicação for atingida */
        if(N == 0)
            break;

        /* Inicalização do grafo */
        tempo = 0;
        for(int i = 1; i <= N; i++){
            /* Vertices */
            vertices[i].cor = BRANCO;
            vertices[i].num = i;
            vertices[i].anterior = NULL;

            /* Arestas & Distâncias & Caminho */
            for(int j = 1; j <= N; j++){
                grafo[i][j] = 0;
                dist[i][j] = INFINITY_VALUE;
                parente[i][j] = NULO;
            }
            
            /* Distâncias Diagonal */
            dist[i][i] = 0;
            parente[i][i] = i;
       }

        for(int i = 1; i < N; i++){
            /* Inicialização das arestas informadas pelo usuario*/
            int x;
            int y;

            cin >> x;
            cin >> y;

            /* Aqui temos um grafo não direcionado com custo igual para os dois lados*/
            grafo[x][y] += 1;
            grafo[y][x] += 1;
            dist[x][y] = 1;
            dist[y][x] = 1;
            parente[x][y] = x;
            parente[y][x] = y;
        }

        /* Executa o algoritm de Floyd Warshall e retorna o nó de "centro" */
        int resultado = 1;
        if(N > 1){
            resultado = FloydWarshall();
        }

        /* Imprime uma linha em branco entre os testes*/
        if(z > 1){
            cout << '\n';
        }

        /* Imprime o resultado obtido */
        cout << "Teste " << z << '\n';
        cout << resultado << '\n';

        /* Incrementa o número do teste */
        z += 1;
    }while(N != 0);

    return 0;
}
<file_sep>/Lista_IV/EDIST.cpp
#include <bits/stdc++.h>

#define MAX_STRING_SIZE 2001

#define max(A, B) (A > B ? A : B)
#define min(A, B) (A < B ? A : B)

#define delete_char(MATRIX, A, B) (MATRIX[A - 1][B])
#define insert_char(MATRIX, A, B) (MATRIX[A][B - 1])
#define modify_char(MATRIX, A, B) (MATRIX[A - 1][B - 1])

using namespace std;

char str1[MAX_STRING_SIZE];
char str2[MAX_STRING_SIZE];

int edit_distance[MAX_STRING_SIZE + 1][MAX_STRING_SIZE + 1] = {{ 0 }};

int main(){
	int minimum_edit_distance;

	int n;

	scanf("%d%*c", &n);

	for(int t = 0; t < n; t++){
		scanf("%s%*c", str1);
		scanf("%s%*c", str2);

		int size_str1 = strlen(str1);
		int size_str2 = strlen(str2);

		int max_str_size = max(size_str1, size_str2);

		for(int i = 0; i <= max_str_size; i++){
			if(i <= size_str1){
				edit_distance[i][0] = i;
			}
			if(i <= size_str2){
				edit_distance[0][i] = i;
			}
		}

		for(int i = 1; i <= size_str1; i++){
			for(int j = 1; j <= size_str2; j++){
				if(str1[i - 1] == str2[j - 1]){
					edit_distance[i][j] = edit_distance[i - 1][j - 1];
				}
				else{
					edit_distance[i][j] = 1 + min(	min(delete_char(edit_distance, i, j),
														insert_char(edit_distance, i, j)),
													modify_char(edit_distance, i, j));
				}
			}
		}

#ifdef DEBUG
		printf("%s:%s\n", str1, str2);
		printf("%6c", ' ');
		for(int i = 0; i < size_str2; i++){
			printf("%3c", str2[i]);
		}
		printf("\n");
		for(int i = 0; i <= size_str1; i++){
			printf("%3c", (i == 0 ? ' ' : str1[i - 1]));
			for(int j = 0; j <= size_str2; j++){
				printf("%3d", edit_distance[i][j]);
			}
			printf("\n");
		}
#endif

		minimum_edit_distance = edit_distance[size_str1][size_str2];

		printf("%d\n", minimum_edit_distance);
	}

	return EXIT_SUCCESS;
}