Les algorithmes de graphes sont fondamentaux pour résoudre de nombreux problèmes en informatique. Cette exploration se concentre sur deux applications classiques : la détection des points d'articulation et des ponts dans les graphes non orientés, et le calcul du chemin critique pour l'ordonnancement de tâches dans les graphes orientés acycliques (DAGs).

Partie 1: Détection de Points d'Articulation et de Ponts

Description du Problème

L'objectif est d'identifier, dans un graphe non orienté et connexe, les points d'articulation (ou sommets coupants) et les ponts (ou arêtes coupantes). Un point d'articulation est un sommet dont la suppression, ainsi que toutes ses arêtes incidentes, augmente le nombre de composantes connexes du graphe. Un pont est une arête dont la suppression a le même effet.

Spécifications d'Entrée

• La première ligne contient un entier unique, N, représentant le nombre total de sommets (numérotés de 0 à N-1).
• Les lignes suivantes décrivent les arêtes du graphe. Chaque ligne contient deux entiers, u et v, indiquant l'existence d'une arête entre le sommet u et le sommet v. Chaque arête est mentionnée une seule fois (par exemple, 0 2 et non 2 0). La lecture des arêtes se termine à la fin de l'entrée.

Spécifications de Sortie

• La première ligne de la sortie doit afficher la phrase suivante en pinyin: wo yi yue du guan yu chao xi de shuo ming. Cette ligne confirme la prise de connaissance des règles anti-plagiat.
• Ensuite, tous les points d'articulation doivent être listés, chacun sur une nouvelle ligne, triés par ordre croissant de leur identifiant.
• Enfin, tous les ponts doivent être listés, chacun sur une nouvelle ligne. Un pont (u, v) est toujours affiché avec u < v. Les ponts sont triés lexicographiquement (par exemple, (0, 2) est avant (0, 3), qui est avant (1, 5)).

Concepts Algorithmiques

L'approche repose sur une adaptation de l'algorithme de Tarjan pour les graphes, en utilisant un parcours en profondeur (DFS) pour calculer deux valeurs critiques pour chaque sommet u:

• temps_decouverte[u]: Le temps (ou ordre) auquel le sommet u a été visité pour la première fois lors du parcours DFS.
• plus_bas_lien[u]: Le plus petit temps_decouverte atteignable depuis u ou l'un de ses descendants dans l'arbre DFS, en utilisant au plus une arête de retour (back-edge).

Ces valeurs permettent d'identifier les points d'articulation et les ponts selon les critères suivants:

• Point d'Articulation:
  • Si u est la racine de l'arbre DFS et a au moins deux enfants dans cet arbre DFS.
  • Si u n'est pas la racine de l'arbre DFS et il existe un enfant v de u tel que plus_bas_lien[v] ≥ temps_decouverte[u].
• Pont:
  • Une arête (u, v) est un pont si v est un enfant de u dans l'arbre DFS et plus_bas_lien[v] > temps_decouverte[u].

Implémentation en C++

Pour des raisons d'efficacité spatiale, les listes d'adjacence sont implémentées avec std::vector<int>. La gestion des temps de découverte et des plus bas liens est centralisée pour une meilleure clarté. La fonction DFS est encapsulée pour permettre une initialisation propre et un appel simple. Les résultats sont collectés dans des vecteurs et sets pour assurer le tri et l'unicité des éléments.

#include <iostream>
#include <vector>
#include <algorithm>
#include <set> // Utilisé pour collecter les ponts afin de les trier et de gérer les doublons automatiquement

// Fonction DFS récursive pour la détection des points d'articulation et des ponts
void detecter_caracteristiques_graphe_dfs(
    int u,
    int parent,
    int& compteur_temps,
    std::vector<int>& temps_decouverte,
    std::vector<int>& plus_bas_lien,
    std::vector<bool>& est_visite,
    const std::vector<std::vector<int>>& adjacence_graphe,
    std::vector<int>& points_articulation_trouves,
    std::set<std::pair<int, int>>& ponts_trouves_set) {

    est_visite[u] = true;
    temps_decouverte[u] = plus_bas_lien[u] = ++compteur_temps;
    int nombre_enfants_dfs = 0;

    for (int v : adjacence_graphe[u]) {
        if (v == parent) { // Ignorer l'arête vers le parent dans l'arbre DFS
            continue;
        }

        if (est_visite[v]) { // v est déjà visité, c'est une arête de retour
            plus_bas_lien[u] = std::min(plus_bas_lien[u], temps_decouverte[v]);
        } else { // v n'est pas visité, explorer cette branche
            nombre_enfants_dfs++;
            detecter_caracteristiques_graphe_dfs(
                v, u, compteur_temps, temps_decouverte, plus_bas_lien, est_visite,
                adjacence_graphe, points_articulation_trouves, ponts_trouves_set);

            plus_bas_lien[u] = std::min(plus_bas_lien[u], plus_bas_lien[v]);

            // Vérifier si u est un point d'articulation
            if (plus_bas_lien[v] >= temps_decouverte[u] && parent != -1) {
                points_articulation_trouves.push_back(u);
            }

            // Vérifier si l'arête (u, v) est un pont
            if (plus_bas_lien[v] > temps_decouverte[u]) {
                ponts_trouves_set.insert({std::min(u, v), std::max(u, v)});
            }
        }
    }

    // Cas spécial: Si u est la racine de l'arbre DFS et a au moins deux enfants, c'est un point d'articulation.
    if (parent == -1 && nombre_enfants_dfs >= 2) {
        points_articulation_trouves.push_back(u);
    }
}

int main() {
    std::ios_base::sync_with_stdio(false); // Optimisation I/O
    std::cin.tie(NULL);                   // Optimisation I/O

    int nombre_sommets = 0;
    std::cin >> nombre_sommets;

    std::vector<:vector>> adjacence_graphe(nombre_sommets);

    int u_edge, v_edge;
    // Lire les arêtes jusqu'à la fin de l'entrée ou une entrée non numérique
    while (std::cin >> u_edge && std::cin >> v_edge) {
        adjacence_graphe[u_edge].push_back(v_edge);
        adjacence_graphe[v_edge].push_back(u_edge); // Graphe non orienté
    }

    int compteur_temps = 0;
    std::vector<int> temps_decouverte(nombre_sommets, 0);
    std::vector<int> plus_bas_lien(nombre_sommets, 0);
    std::vector<bool> est_visite(nombre_sommets, false);
    std::vector<int> points_articulation_trouves;
    std::set<:pair int="">> ponts_trouves_set;

    // Lancer la détection pour chaque composante connexe (le problème indique un graphe connexe, donc un seul appel suffirait de 0)
    for (int i = 0; i < nombre_sommets; ++i) {
        if (!est_visite[i]) {
            detecter_caracteristiques_graphe_dfs(
                i, -1, compteur_temps, temps_decouverte, plus_bas_lien, est_visite,
                adjacence_graphe, points_articulation_trouves, ponts_trouves_set);
        }
    }

    // Tri et élimination des doublons pour les points d'articulation
    std::sort(points_articulation_trouves.begin(), points_articulation_trouves.end());
    points_articulation_trouves.erase(std::unique(points_articulation_trouves.begin(), points_articulation_trouves.end()), points_articulation_trouves.end());

    std::cout << "wo yi yue du guan yu chao xi de shuo ming" << std::endl;

    for (int pa : points_articulation_trouves) {
        std::cout << pa << std::endl;
    }

    for (const auto& bridge : ponts_trouves_set) {
        std::cout << bridge.first << " " << bridge.second << std::endl;
    }

    return 0;
}
</:pair></int></bool></int></int></:vector>

Partie 2: Ordonnancement de Tâches et Chemin Critique

Description du Problème

Un ensemble de N tâches doit être exécuté, chacune ayant une durée prédéfinie. Certaines tâches présentent des dépendances, signifiant qu'une tâche ne peut débuter qu'après la complétion de ses prérequis. Ce scénario est modélisé par un graphe orienté acyclique (DAG) où chaque sommet représente une tâche et chaque arête (B, A) indique que la tâche B dépend de la tâche A (A doit être achevée avant que B puisse commencer). Chaque sommet est pondéré par la durée de la tâche correspondante. L'objectif est de calculer le temps minimal nécessaire pour compléter toutes les tâches, en supposant une disponibilité illimitée de ressources (personnel).

Spécifications d'Entrée

• La première ligne contient un entier unique, N, le nombre total de tâches.
• Les N lignes suivantes spécifient, pour chaque tâche, son identifiant (de 1 à N) et la durée requise pour la compléter. Par exemple, 1 50 signifie que la tâche 1 demende 50 unités de temps.
• Les lignes restantes décrivent les dépendances. Chaque ligne u v signifie que la tâche u dépend de la tâche v. La lecture des dépendances se termine à la fin de l'entrée.

Spécifications de Sortie

• La première ligne de la sortie doit afficher la phrase suivante en anglais: I have read the rules about plagiarism punishment.
• La seconde ligne doit afficher le temps d'exécution total minimal pour l'ensemble des N tâches.

Hypothèse Clé

Le graphe de dépendances est garanti être un Graphe Orienté Acyclique (DAG), évitant ainsi les dépendances circulaires et assuarnt qu'une solution est toujours possbile.

Concepts Algorithmiques

Ce problème se résout en trouvant la longueur du chemin critique dans le DAG, qui est le plus long chemin en termes de somme des durées des tâches. Une approche par parcours en profondeur (DFS) est utilisée pour calculer les temps de début et de fin au plus tôt pour chaque tâche:

• temps_debut_plus_tot[u]: Le moment le plus précoce où la tâche u peut commencer. C'est le maximum des temps_fin_plus_tot[v] pour toutes les tâches v dont u dépend.
• temps_fin_plus_tot[u]: Le moment le plus précoce où la tâche u peut se terminer. Il est calculé comme temps_debut_plus_tot[u] + duree[u].

Le processus DFS doit parcourir le graphe des dépendances de manière récursive. Pour chaque tâche, il s'assure que les temps de fin de toutes ses dépendances sont calculés avant de déterminer son propre temps de début. Le temps total minimal est le maximum de tous les temps_fin_plus_tot calculés pour l'ensemble des tâches.

Implémentation en C++

Les tâches sont indexées de 0 à N-1 pour correspondre aux indices des vecteurs. Le graphe est construit de telle sorte qu'une arête de u vers v signifie que u dépend de v. Cela simplifie le calcul récursif, car le DFS explore les dépendances avant de remonter.

#include <iostream>
#include <vector>
#include <algorithm>

// Structure pour stocker les temps de début et de fin au plus tôt pour chaque tâche
struct InfoTempsTache {
    int debut_plus_tot; // Temps de début au plus tôt
    int fin_plus_tot;   // Temps de fin au plus tôt

    InfoTempsTache() : debut_plus_tot(0), fin_plus_tot(0) {}
};

// Fonction DFS pour calculer les temps de début et de fin au plus tôt
void calculer_chemin_critique_dfs(
    int id_tache,
    const std::vector<std::vector<int>>& adjacence_taches,
    const std::vector<int>& durees_taches,
    std::vector<InfoTempsTache>& info_temps_taches,
    std::vector<int>& etat_visite_dfs) {

    etat_visite_dfs[id_tache] = 1; // Marquer comme "en cours de visite"

    int max_fin_prerequis = 0; // Maximum des temps de fin de toutes les dépendances

    // Parcourir toutes les tâches dont id_tache dépend
    for (int prerequis_id : adjacence_taches[id_tache]) {
        if (etat_visite_dfs[prerequis_id] == 0) { // Si la dépendance n'a pas encore été visitée
            calculer_chemin_critique_dfs(
                prerequis_id, adjacence_taches, durees_taches, info_temps_taches, etat_visite_dfs);
        }
        // Après le retour de l'appel récursif (ou si déjà visité), prendre le temps de fin de cette dépendance
        max_fin_prerequis = std::max(max_fin_prerequis, info_temps_taches[prerequis_id].fin_plus_tot);
    }

    info_temps_taches[id_tache].debut_plus_tot = max_fin_prerequis;
    info_temps_taches[id_tache].fin_plus_tot = info_temps_taches[id_tache].debut_plus_tot + durees_taches[id_tache];
    etat_visite_dfs[id_tache] = 2; // Marquer comme "visité"
}

int main() {
    std::ios_base::sync_with_stdio(false); // Optimisation I/O
    std::cin.tie(NULL);                   // Optimisation I/O

    int nombre_taches = 0;
    std::cin >> nombre_taches;

    std::vector<int> durees_taches(nombre_taches, 0);
    std::vector<infotempstache> info_temps_taches(nombre_taches);
    std::vector<int> etat_visite_dfs(nombre_taches, 0);
    std::vector<:vector>> adjacence_taches(nombre_taches);

    // Lire les durées des tâches
    for (int i = 0; i < nombre_taches; ++i) {
        int id_tache_input;
        std::cin >> id_tache_input; // IDs de 1 à N
        std::cin >> durees_taches[id_tache_input - 1]; // Stocker à l'indice 0 à N-1
    }

    // Lire les dépendances (u dépend de v)
    int u_dependant, v_prerequis;
    // La boucle continue tant que la lecture est possible (jusqu'à EOF ou entrée non numérique).
    while (std::cin >> u_dependant && std::cin >> v_prerequis) {
        // Ajouter une arête de u_dependant à v_prerequis (u_dependant dépend de v_prerequis)
        adjacence_taches[u_dependant - 1].push_back(v_prerequis - 1);
    }

    // Lancer le DFS pour toutes les tâches pour s'assurer de couvrir tous les chemins,
    // car le graphe peut avoir plusieurs composantes ou "sources" logiques.
    for (int i = 0; i < nombre_taches; ++i) {
        if (etat_visite_dfs[i] == 0) {
            calculer_chemin_critique_dfs(
                i, adjacence_taches, durees_taches, info_temps_taches, etat_visite_dfs);
        }
    }

    // Trouver le temps de fin maximal parmi toutes les tâches
    int temps_minimal_total = 0;
    for (int i = 0; i < nombre_taches; ++i) {
        temps_minimal_total = std::max(temps_minimal_total, info_temps_taches[i].fin_plus_tot);
    }

    std::cout << "I have read the rules about plagiarism punishment" << std::endl;
    std::cout << temps_minimal_total << std::endl;

    return 0;
}
</:vector></int></infotempstache></int>