Aller au contenu principal

TD 15/12

Quentin Fortier
Quentin Fortier
Professeur d'informatique
  • Fin TD "Décidabilité et complexité".
  • En MPI* : TD "Algorithme d'approximation" exo 1.

LeetCode 4 : Find Edges in Shortest Paths

Quentin Fortier
Quentin Fortier
Professeur d'informatique

Exercice à faire en C sur LeetCode cette semaine : https://leetcode.com/problems/find-edges-in-shortest-paths/description/

Il y a deux indices en bas de la page (Hint).

Details

Indice Pour passer tous les tests, il faut implémenter l'algorithme de Dijkstra ce qui demande une file de priorité (tas min) et est un peu long à implémenter... On pourrait implémenter Floyd-Warshall ou Bellman-Ford à la place.

Solution
#include <stdbool.h>

int** createGraph(int n, int** edges, int edgesSize, int* edgesColSize) { // matrice d'adjacence
    int **g = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        g[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++)
            g[i][j] = -1;
    }
    for (int i = 0; i < edgesSize; i++) {
        int a = edges[i][0];
        int b = edges[i][1];
        int w = edges[i][2];
        g[a][b] = w;
        g[b][a] = w;
    }
    return g;
}

int** floydWarshall(int n, int** g) {
    int** dist = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        dist[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            if (i == j)
                dist[i][j] = 0;
            else if (g[i][j] != -1)
                dist[i][j] = g[i][j];
            else
                dist[i][j] = 1e9;
        }
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
    return dist;
}

bool* findAnswer(int n, int** edges, int edgesSize, int* edgesColSize, int* returnSize) {
    int** g = createGraph(n, edges, edgesSize, edgesColSize);
    int** dist = floydWarshall(n, g);
    bool* answer = (bool*)malloc(edgesSize * sizeof(bool));
    for (int i = 0; i < edgesSize; i++) {
        int a = edges[i][0];
        int b = edges[i][1];
        int w = edges[i][2];
        if (dist[0][a] + w + dist[b][n - 1] == dist[0][n - 1] ||
            dist[0][b] + w + dist[a][n - 1] == dist[0][n - 1])
            answer[i] = true;
        else
            answer[i] = false;
    }
    *returnSize = edgesSize;
    for (int i = 0; i < n; i++) {
        free(g[i]);
        free(dist[i]);
    }
    free(g);
    free(dist);
    return answer;
}

Colle 2

Quentin Fortier
Quentin Fortier
Professeur d'informatique
  • Graphes : révisions de MP2I.
  • Kruskal et Union-Find : tout le cours.
  • Composantes fortement connexes et Kosaraju : tout le cours.
  • Couplages : tout le cours.
  • Plus courts chemins et A* : tout le cours.
  • Décidabilité : tout le cours. Pas encore les classes de complexité.

LeetCode 3 : Possible Bipartition

Quentin Fortier
Quentin Fortier
Professeur d'informatique

Exercice à faire en C sur LeetCode, avant lundi prochain : https://leetcode.com/problems/possible-bipartition

Solution
bool dfs(int u, int c, int* colors, int** g, int n) {
    colors[u] = c;
    for (int v = 1; v <= n; v++) {
        if (g[u][v]) { // il y a une arête entre u et v
            if (colors[v] == 0) {
                if (!dfs(v, -c, colors, g, n))
                    return false;
            } else if (colors[v] == c) {
                return false;
            }
        }
    }
    return true;
}

bool possibleBipartition(int n, int** dislikes, int dislikesSize, int* dislikesColSize) {
    int* colors = (int*)calloc(n + 1, sizeof(int)); // 0: non coloré, 1: rouge, -1: bleu
    int** g = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++)
        g[i] = (int*)calloc(n + 1, sizeof(int));
    for (int i = 0; i < dislikesSize; i++) {
        int u = dislikes[i][0];
        int v = dislikes[i][1];
        g[v][u] = g[u][v] = 1;
    }

    for (int i = 1; i <= n; i++) {
        if (colors[i] == 0 && !dfs(i, 1, colors, g, n))
            return false;
    }
    return true;
}