OJ Board

Code: Select all

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

#define LETTERS_NUM 26
#define TRUE 1
#define FALSE 0


typedef unsigned char BOOLEAN;
typedef unsigned char UINT8;
typedef struct word_t
{
    char str[20];
    struct word_t *next;
} word;

typedef struct graph_node_t
{
    UINT8 smalls_num;
    UINT8 bigs_num;
    BOOLEAN participates;
    BOOLEAN small[LETTERS_NUM];
    BOOLEAN big[LETTERS_NUM];    
} graph_node;



int main()

{
    // Declarations
    word *words_head,*words_tail,*tmp;
    graph_node order_graph[LETTERS_NUM];
    UINT8 letter_order[LETTERS_NUM];
    int word_count = 0;
    int index1,index2;
    int letter_count = 0;
    int letter_count1;
    int letter_rank = 1;
    
    
    // Input of words;
    tmp = (word*)malloc(sizeof(word));
    scanf("%s",tmp->str);
    words_head = tmp;
    words_tail = words_head;
    
    while (strcmp(words_tail->str , "#")!= 0)
    {
        word_count++;
        tmp = (word*)malloc(sizeof(word));
        scanf("%s",tmp->str);
        words_tail ->next = tmp;
        words_tail = words_tail->next;
    }
    if (word_count == 0)
        return 0;
    
    // fill in the order graph
    memset(order_graph,0,sizeof(order_graph));
    
    tmp = words_head;
    while (strcmp((tmp->next)->str , "#")!= 0)
    {
        char* str1 = tmp->str;
        char* str2 = (tmp->next)->str;
        
        while ((*str1 == *str2) && (*str1++ != '\0') && (*str2++ != '\0'));
        
        if ((*str1 != '\0') && (*str2 != '\0'))
        {
            if (FALSE == order_graph[*str1 - 'A'].participates)
            {
                order_graph[*str1 - 'A'].participates = TRUE;
                letter_count++;
            }
            order_graph[*str1 - 'A'].bigs_num++;
            order_graph[*str1 - 'A'].big[*str2 - 'A'] = TRUE;
            if (FALSE == order_graph[*str2 - 'A'].participates)
            {
                order_graph[*str2 - 'A'].participates = TRUE;
                letter_count++;
            }
            order_graph[*str2 - 'A'].smalls_num++;
            order_graph[*str2 - 'A'].small[*str1 - 'A'] = TRUE;        
        }
        
        tmp  = tmp->next;
        
        
    }
    
    memset ( letter_order,0,LETTERS_NUM);
    letter_count1 = letter_count;
    while (letter_count > 0)
    {
        index1 = 0;
        while ((FALSE == order_graph[index1].participates) || (TRUE == order_graph[index1].participates && order_graph[index1].smalls_num > 0))
            index1++;
        order_graph[index1].participates = FALSE;
        letter_order[index1] = letter_rank++;
        for (index2 = 0 ; index2 < LETTERS_NUM ; index2++)
        {
            if (TRUE == order_graph[index1].big[index2])
            {
                order_graph[index2].small[index1] = FALSE;
                order_graph[index2].smalls_num--;
            }
        
        }
        
        letter_count--;
    
    }
    
    index1 = 1;
    while (index1 <= letter_count1)
    {
        index2=0;
        while (letter_order[index2] != index1)
            index2++;
        
        printf("%c", index2 + 'A');
        
        
        index1++; 
    
    }
    
    printf("\n");
    

    return 0;
}

Code: Select all

Input 1 : 
QEWR
YSFDG
IOU
BASERB
BKUI
LKJN
YHDF
EWRRW
BDQ
#

Output 1:
QYIBLESOAKHWDFUJRNG

Input 2 :
REFEW
EGBA
ILR
#

Output 2:
REIGLFBAW

Code: Select all

#include <cstdio>
#include <cstring>

bool m[26][26];
int ind[26];
bool used[26];

void cmp(char a[],char b[]){
	for(int i=0;a[i]&&b[i];++i)
		if( a[i] != b[i] ){
			int t1 = a[i]-'A';
			int t2 = b[i]-'A';
			m[t1][t2] = 1;
			used[t1] = used[t2] = 1;
			++ind[t2];
			return;
		}
}

int main(){
	
	char last[100];
	char now[100];
	bool only = 1;
	
	scanf("%s",last);
	
	while(1){	
		scanf("%s",now);		
		if( now[0] == '#' ) break;

		only = 0;
		cmp(last,now);
		strcpy(last,now);
	}
	
	int q[26];
	int qf = 0 , qn = 0;
	
	for(int i=0;i<26;++i)
		if( used[i] && ind[i]==0 )
			q[qn++] = i;
	
	while( qf < qn ){
		int f = q[qf++];
		printf("%c",'A'+f);
		for(int i=0;i<26;++i)
			if( m[f][i] ){
				--ind[i];
				if( ind[i] <= 0 ) q[qn++] = i;
			}
	}
	
	if( only ) printf("%c",last[0]);
	
	printf("\n");

	return 0;
}

Code: Select all

import java.util.*;
import java.io.*;
 
class Stack<T> {
        private LinkedList<T> storage = new LinkedList<T>();
        public void push(T v) {storage.addFirst(v);}
        public T peek() {return storage.getFirst();}
        public T pop() {return storage.removeFirst();}
        public boolean isEmpty() {return storage.isEmpty();}
        public String toString() {return storage.toString();}
}
 
public class Main 
{
        static int[][]  a = new int[128][128];
        static boolean[] used = new boolean[128];
        static boolean[] exist = new boolean[128];
        static boolean[] letterUsed = new boolean[128];
        static Stack<Character> q = new Stack<Character>();
 
        static Scanner sc = new Scanner(System.in);
    static PrintWriter pw = new PrintWriter(System.out);
 
   /*
    * function for search in s1 and s2 first different characters
    * if s1 equals s2 then return -1
    * else first different character index
    */
   static void usingLetters(String s1) {
           for(int i = 0; i < s1.length(); i++) {
                   letterUsed[s1.charAt(i)] = true; 
           }
   }
   static int strcmp(String s1, String s2) {
           
           for(int i = 0; i < Math.min(s1.length(), s2.length()); i++)
                   if(s1.charAt(i) != s2.charAt(i)) {
                           return i;
                   }
           
           return -1;
   }
        
    static void dfs(int v) {
        used[v] = true; 
        for(int i = 0; i < 128; i++) 
                if (a[v][i] == 1 && !used[i]) {
                        dfs(i); 
                }
        q.push((char)v);
    }
    
    static void topSort() {
        for(int i = 127; i >= 0; i--)
        {
                if(!used[i] && letterUsed[i] && i != '#')
                        dfs(i);
        }
    }
    
    
    
        public static void main(String[] args) throws IOException {
       
        try
        {
                String s1,s2;
                s1 = sc.nextLine();
                if(s1.charAt(0) == '#')
                        return;
                usingLetters(s1);
                do {
                        
                        s2 = sc.nextLine();
                                if(s2.charAt(0) == '#')
                                        break;
                        usingLetters(s2);
                    int i = strcmp(s1,s2);
 
                        if(i != -1) 
                                a[s1.charAt(i)][s2.charAt(i)] = 1;
                        
                        s1 = s2;
                        
                } while(true);
                
 
                topSort();
                
                while(!q.isEmpty()) {
                        pw.print(q.pop());
                }
 
        }
        finally
        {
                pw.close();
        }
        }
        
}