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
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 :
- the graph is connected
- incoming edges count equals outgoing edges count for each vertex
Code :
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#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;
}
int main(){
int numTest;
scanf( "%d", &numTest );
while( numTest-- )
performTest();
return 0;
}
#include<stdlib.h>
#include<string.h>
#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;
}
int main(){
int numTest;
scanf( "%d", &numTest );
while( numTest-- )
performTest();
return 0;
}
Acknowledgments :
Abhishek Kumar (abhishek.kumar.cse08@itbhu.ac.in)
No comments:
Post a Comment