LeetCode 8

Exercice à faire en C sur LeetCode pendant les vacances de Noël : https://leetcode.com/problems/find-champion-ii (facile)

Et pour ceux qui veulent plus difficile : https://leetcode.com/problems/shortest-cycle-in-a-graph

Indice

Pour le premier exercice, il s'agit de trouver s'il existe un unique sommet de degré entrant nul.

Pour le deuxième exercice, on peut utiliser un parcours en largeur : si on est en train de visiter un sommet u et qu'on trouve un voisin v de u qui est déjà visité, alors on a trouvé un cycle de longueur d[u] + d[v] + 1.

Solution

int findChampion(int n, int** edges, int edgesSize, int* edgesColSize) {
    int** g = (int**)malloc(sizeof(int*) * n);
    for (int i = 0; i < n; i++) {
        g[i] = (int*)malloc(sizeof(int) * n);
        for (int j = 0; j < n; j++)
            g[i][j] = 0;
    }
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1];
        g[u][v] = 1;
    }
    int c = -1;
    for(int j = 0; j < n; j++) {
        int deg = 0;
        for (int i = 0; i < n; i++)
            deg += g[i][j];
        if(deg == 0) {
            if(c != -1) {
                return -1;
            }
            c = j;
        }
    }
    return c;
}