Deux exercices d'algorithmique sur les graphes sont présentés : l'un sur le tri topologique avec vérification de cycle, l'autre sur l'algorithme de Dijkstra pour la recherche du chemin le plus court.

Exercice 1 : Tri topologique des tâches

Un projet est divisé en n sous-tâches, identifiées de 0 à n-1. Pour achever le projet, toutes les sous-tâches doivent être complétées. Des contraintes de précédence existent entre certaines sous-tâches. Écrivez un programme qui détermine un ordre d'exécution valide. Si le projet est irréalisable (présence d'un cycle), le programme doit le signaler.

Format d'entrée

La première ligne contient deux entiers n et e, chacun inférieur ou égal à 100, représentant le nombre de sous-tâches et le nombre de relations de précédence. Les e lignes suivantes contiennent chacune deux entiers a et b, indiquant que la tâche a doit précéder la tâche b.

Format de sortie

Si le projet est irréalisable, affichez « unworkable project ». Sinon, affichez une seule ligne contenant les numéros des n sous-tâches séparés par des espaces, représentant l'ordre d'exécution. Si plusieurs ordres sont possibles, produisez celui de lexicographique le plus petit (par exemple, 1 2 3 9 est plus petit que 1 2 4 5).

Exemple d'entrée 1

3 2
0 1
1 2

Exemple de sortie 1

0 1 2

Exemple d'entrée 2

3 3
0 1
1 2
2 0

Exemple de sortie 2

unworkable project

Solution en C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAX_NODES = 101;
vector<int> adjacencyList[MAX_NODES];
priority_queue<int, vector<int>, greater<int>> minHeap;
vector<int> resultOrder;
int inDegree[MAX_NODES] = {0};

int main() {
    int numNodes, numEdges;
    cin >> numNodes >> numEdges;
    for (int i = 0; i < numEdges; i++) {
        int from, to;
        cin >> from >> to;
        adjacencyList[from].push_back(to);
        inDegree[to]++;
    }
    for (int i = 0; i < numNodes; i++) {
        if (inDegree[i] == 0) {
            minHeap.push(i);
        }
    }
    while (!minHeap.empty()) {
        int current = minHeap.top();
        minHeap.pop();
        resultOrder.push_back(current);
        for (int neighbor : adjacencyList[current]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                minHeap.push(neighbor);
            }
        }
    }
    if (resultOrder.size() == numNodes) {
        for (int node : resultOrder) {
            cout << node << " ";
        }
    } else {
        cout << "unworkable project";
    }
    return 0;
}

Exerciec 2 : Problème du messager

En temps de guerre, il y a n postes de garde, connectés par des lignes de communication. Un messager transmet des messages entre les postes, avec un temps de déplacement en jours. Le quartier général est au poste 1. Lorsqu'un ordre est donné, des messagers partent vers les postes connectés. À réception, chaque poste envoie ses propres messagers, et ainsi de suite jusqu'à ce que tous les postes aient reçu le message. Chaque poste dispose d'assez de messagers pour ses connexions. Calculez le temps minimum pour que tous les postes reçoivent le message. Si ce n'est pas possible, retournez -1.

Format d'entrée

La première ligne contient deux entiers n et m (1≤n≤100), représentant le nombre de postes et le nombre de lignes de communication. Les m lignes suivantes contiennent trois entiers i, j, k, indiquant une connexion bidirectionnelle entre i et j avec un temps de k jours.

Format de sortie

Affichez un entier : le temps minimum pour diffuser le message à tous les postes, ou -1 si tous les postes ne sont pas atteignables.

Exemple d'entrée

4 4
1 2 4
2 3 7
2 4 1
3 4 6

Exemple de sortie

11

Solution en C++ avec l'algorithme de Dijkstra

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int MAX_POSTS = 101;
typedef pair<int, int> WeightNode;
int shortestPathFound[MAX_POSTS];
int minDist[MAX_POSTS];

struct Connection {
    int destination;
    int travelDays;
};

vector<Connection> graph[MAX_POSTS];

void initialize() {
    memset(minDist, 0x3f, sizeof(minDist));
    memset(shortestPathFound, 0, sizeof(shortestPathFound));
}

void dijkstra(int start) {
    priority_queue<WeightNode, vector<WeightNode>, greater<WeightNode>> pq;
    pq.push(make_pair(0, start));
    while (!pq.empty()) {
        WeightNode top = pq.top();
        pq.pop();
        int u = top.second;
        if (shortestPathFound[u]) continue;
        shortestPathFound[u] = 1;
        for (const auto& edge : graph[u]) {
            int v = edge.destination;
            int weight = edge.travelDays;
            if (!shortestPathFound[v] && minDist[v] > minDist[u] + weight) {
                minDist[v] = minDist[u] + weight;
                pq.push(make_pair(minDist[v], v));
            }
        }
    }
}

int main() {
    int numPosts, numConnections;
    cin >> numPosts >> numConnections;
    initialize();
    for (int i = 0; i < numConnections; i++) {
        int from, to, days;
        cin >> from >> to >> days;
        graph[from].push_back({to, days});
        graph[to].push_back({from, days});
    }
    minDist[1] = 0;
    dijkstra(1);
    int maxTime = -1;
    for (int i = 1; i <= numPosts; i++) {
        if (minDist[i] == 0x3f3f3f3f) {
            maxTime = -1;
            break;
        }
        if (minDist[i] > maxTime) {
            maxTime = minDist[i];
        }
    }
    cout << maxTime << endl;
    return 0;
}