1. 

package acm_200_rare_order;

/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: acm_200_rare_order
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=46&page=show_problem&problem=136
*
* @author Martin Lambeck
* @version 1.0, 10.08.2010
*
* Method : ad-hoc
* Status : Accepted
* Runtime: 0.264
*/

import java.util.Arrays;
import java.util.Scanner;

public class Main
{
static Scanner sc = new Scanner(System.in);

static char[] old = new char[20]; //previous line of input

static boolean[][] rel = new boolean[26][26];//adjacency matrix. true if the input gave the relation index1 < index2 (no derived relations!)

static int[] rel2 = new int[26]; // 99 char doesnt appear; <99 number of distinct x where input gave the relation x < index (no derived relations!)

public static void main(String... args)
{
Arrays.fill(rel2, 99);

work();


int l = 0;
String str = "";

while ((l = getBest()) >= 0)
{
for (int i = 0; i < rel.length; i++)
{
if (rel[l][i]) //if there was a first order relation
rel2[i]--; //reduce the dependecie count
}

rel2[l] = 99; //dont consider this char anymore

str += unmap(l);
}

System.out.println(str);
}

//get the next char that has no dependecies like x < char
public static int getBest ()
{
for (int i = 0; i < rel2.length; i++)
if (rel2[i] == 0)
return i;

return -1; //no such char
}

public static void work()
{
while (true)
{
char[] chr = new char[20];

String line = sc.nextLine();

if (line.equals("#")) //end of input
return;

line.getChars(0, line.length(), chr, 0); //read line into char array


for (int i = 0; i < 20; i++) //search first index where the character is different from the one in the previous line
{
if (chr[i] == old[i]) //character is the same as in the previous line, consider next pair of chars
continue;

if (rel2[map(chr[i])] == 99) //set that this char has appeared
rel2[map(chr[i])] = 0;


if (old[i] != '\0') //the previous line hasnt ended (end of current line cant happen)
{
if (!rel[map(old[i])][map(chr[i])]) //if this first order relation hasnt been tracked yet
rel2[map(chr[i])] += 1; //add one to the counter

rel[map(old[i])][map(chr[i])] = true; //the relation has been tracked
}

break;
}

old = chr; //set current line as old line
}
}

//returns array index for given char
public static int map(char c)
{
return ((int) c) - ((int) 'A');
}

//returns char for given array index
public static char unmap(int i)
{
return (char) (i + ((int) 'A'));
}
}



2.

package problemSetVolumes.volume002;

import java.util.*;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 200 - Rare Order
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=46&page=show_problem&problem=136
*
* @author Siegfried Ippisch
* @version 1.0
*
* Method : Topological sorting
* Status : Accepted
* Runtime: 0.344
*/
public class RareOrder {

static class Order{
boolean[][] matrix = new boolean[26][26];
int[] count = new int[26]; // count outgoing edges
List<Integer> n = new ArrayList<Integer>(26); // used Charakters

String last = null;

void add(String str){
selChars(str);
if(last != null)
bulidMatrix(last,str);
last = str;
}

void selChars(String str){
for(int c: str.toCharArray()){
c-='A';
if(!n.contains(c))
n.add(c);
}
}

void bulidMatrix(String first, String seccond){
int minLength = Math.min(seccond.length(), first.length());
for(int i=0; i<minLength; i++){
int c1 = first.charAt(i)-'A';
int c2 = seccond.charAt(i)-'A';
if(c1 != c2){
if(!matrix[c1][c2]){
matrix[c1][c2] = true;
count[c1]++;
}
break;
}
}
}

List<Integer> getOrder(){
List<Integer> order = new ArrayList<Integer>(26);
for(int c=n.size(); c>=0; c--)
for(int i: n)
if(count[i] == 0){
order.add(i);
count[i] = -1;
for(int j: n)
if(matrix[j][i]){
matrix[j][i] = false;
count[j]--;
}
}
return order;
}
}

public static void main(String[] args){

Scanner in = new Scanner(System.in);

while(in.hasNext()){

Order o = new Order();

String next = in.next();
while(!next.equals("#")){
o.add(next);
next = in.next();
}

String out = "";
for(int i: o.getOrder())
out = (char)(i+'A') +out;
System.out.println(out);
}

in.close();
}

}


3.


/**
* ACM Training 2009
* ACM Problem #200 - Rare Order
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=136
*
* @author Dennis Wilfert
* @version 1.0, 11/03/2009
*
* Methode: Topologische Sortierung
* Status : Accepted
* Runtime: 0.124
*/

import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.LinkedList;

class Main {

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));

LinkedList<Character> l = new LinkedList<Character>();

boolean[] exists = new boolean[26];

char[][] chr = new char[10000][];
int line = 0;
int length = 1;
int maxlength = 0;
int index, j, i;
while (true) {

chr[line] = reader.readLine().toCharArray();
if (maxlength < chr[line].length) {
maxlength = chr[line].length;
}

if (chr[line][0] == '#') {
break;
}

line++;

}
for (i = 0; i < line; i++) {

if (!exists[chr[i][0] - 65]) {
l.addLast(chr[i][0]);
exists[chr[i][0] - 65] = true;
}
}

while (length < maxlength) {
for (i = 0; i < line - 1; i++) {
if (length == chr[i].length - 1 && length == chr[i + 1].length - 1) {
j = 0;
while (chr[i][j] == chr[i + 1][j])
j++;

if (j == length) {
if (exists[chr[i][j] - 65] && !exists[chr[i + 1][j] - 65]) {
index = l.indexOf(chr[i][j]);
l.add(index + 1, chr[i + 1][j]);
exists[chr[i + 1][j] - 65] = true;
}
if (!exists[chr[i][j] - 65] && exists[chr[i + 1][j] - 65]) {
index = l.indexOf(chr[i + 1][j]);
l.add(index, chr[i][j]);
exists[chr[i][j] - 65] = true;
}
}

}
}
length++;
}

for (char c : l) {
writer.print(c);
}
writer.println();
writer.flush();

}
}