celebrity.c

/*
    celebrity.c
    Author: George Lesica
    Description: An implementation of the celebrity 
    graph algorithm.
*/

#include <stdlib.h>
#include <stdio.h>

int celebrity(int **graph, int size) {
    int current = 0;
    int next = 1;

    /* Start with vertex 1, attempt to move to vertex 
    2, then 3, etc. until we find a vertex we can get 
    to. Move to that vertex and start over, attempting 
    to move to vertex n+1. Once we have attempted to 
    move to the last vertex, which ever one we're at 
    is the only possible candidate to be a 
    "celebrity". */
    while (next < size) {
        if (graph[current][next] == 1) {
            current = next;
        }

        next++;
    }

    next = 0;

    /* Verify that the vertex we have identified 
    is actually a "celebrity". */
    while (next < size) {
        if (graph[current][next] == 1) {
            return -1;
        }

        next++;
    }

    return current;
}

int main() {

    /* Read in the number of vertices and edges. */
    int nverts, nedges;
    scanf("%d %d\n", &nverts, &nedges);

    /* Create the blank adjacency array. */
    int **adj = malloc(nverts * sizeof(int *));
    int i;
    for (i = 0; i < nverts; i++) {
        adj[i] = malloc(nverts * sizeof(int));
    }

    /* Read in edge endpoints. */
    int j, k;
    while (nedges > 0) {
        scanf("%d %d\n", &j, &k);
        adj[j][k] = 1;
        nedges--;
    }

    /* Find the celebrity, if present. */
    int result = celebrity(adj, nverts);
    printf("%d\n", result);
}