3) Apresente um algoritmo para, dado um digrafo D=(V,A) e 2 vértices u ev. determinar o número minimos de arcos que devem ter sua orientação trocada para que tenhamos um caminho direcionado de u para v.

Para determinar o número mínimo de arcos que devem ter sua orientação trocada para que tenhamos um caminho direcionado de u para v em um grafo dirigido D=(V,A), podemos usar o algoritmo de Busca em Profundidade (DFS) com uma variante para contar o número de arcos que precisam ser invertidos.<br /><br />A ideia básica é realizar uma busca em profundidade a partir do vértice u e, ao encontrar o vértice v, contar o número de arcos que precisam ser invertidos para formar um caminho direcionado de u para v.<br /><br />Aqui está um exemplo de como esse algoritmo pode ser implementado:<br /><br />1. Inicialize uma variável "cont" para contar o número de arcos que precisam ser invertidos.<br />2. Realize uma busca em profundidade a partir do vértice u, marcando cada vértice visitado.<br />3. Enquanto a busca estiver sendo realizada, verifique se o vértice atual é o vértice v. Se for, pare a busca e retorne o valor da variável "cont".<br />4. Caso contrário, para cada arco (u, w) dirigido de u para w, se w não foi visitado, incremente a variável "cont" e marque w como visitado.<br />5. Se o vértice atual não for o vértice v e não houver mais arcos para explorar, volte ao vértice pai e continue a busca.<br />6. Repita os passos 3 a 5 até que todos os arcos tenham sido explorados ou um caminho direcionado de u para v tenha sido encontrado.<br /><br />Ao final da execução do algoritmo, o valor da variável "cont" será o número mínimo de arcos que precisam ter sua orientação trocada para que tenhamos um caminho direcionado de u para v.