Algorithms Forever ...: Existence of closed chain of words

Algorithms Forever ...: Existence of closed chain of words

You are given a set of words. A chain is formed by joining words W1 and W2 such that last character of W1 is first character of W2. Devise an algorithm to check whether such a closed chain that uses all words in the set exists for given set of words.

Eg.
S = { abc, gha, efg, cde }
Exists : abc-cde-efg-gha

Solution :

The answer to this question is to find existence of Euler circuit in the graph formed by the 26 possible vertices a-z and words being directed edges. We check the following conditions for existence of Euler circuit :

1. the graph is connected
2. incoming edges count equals outgoing edges count for each vertex

#define toNumber(character) (character-97)

int alpha[26][26];
int occur[26], found[26];

typedef struct tList{
    int val;
    struct tList *next;
} *list;

int connected(){
    int i, root;
    int Q[26], color[26], head = 0, tail = -1;

    for( i=0; i<26; i++ ){
        color[i] = 1;
        if( found[i] == 1 ){
            root = i;
            color[i] = -1;
        }
    }

    Q[++tail] = root;

    while( tail >= head ){
        int u = Q[head++];
        color[u] = 1;
        for( i=0; i<26; i++ )
            if( color[i] == -1 && alpha[u][i] == 1 ){
                Q[++tail] = i;
                color[i] = 0;
            }
    }

    for( i=0; i<26; i++ )
        if( color[i] != 1 )
            return 0;

    return 1;
}

int checkEvenDegree(){
    int i;

    for( i=0; i<26; i++ )
        if( occur[i] != 0 )
            return 0;

    return 1;
}

void performTest(){
    int i, j, num;
    scanf( "%d", &num );

    for( i=0; i<26; i++ ){
        occur[i] = 0;
        found[i] = 0;
        for( j=0; j<26; j++ )
            alpha[i][j] = 0;
    }


    char word[1001];

    for( i=0; i<num; i++ ){
        scanf( "%s", word );

        int len = strlen( word );

        found[ toNumber(word[0]) ] = 1;
        found[ toNumber(word[strlen(word)-1]) ] = 1;

        occur[ toNumber(word[0]) ]--;
        occur[ toNumber(word[strlen(word)-1]) ]++;

        alpha[ toNumber(word[0]) ][ toNumber(word[strlen(word)-1]) ] = 1;
    }

    if( checkEvenDegree() && connected() ){
        printf( "Ordering is possible.\n" );
        return;
    }

    printf( "Ordering not possible.\n" );
    return;

}
Related: LeetCode - Word Ladder I
Read full article from Algorithms Forever ...: Existence of closed chain of words