ACM UVa 算法题 #200 - Rare Order的解法

题目链接在这里：ACM UVa #200 - Rare Order

本题的解法相对简单：

对于输入的所有字符串，只需两两比较，每个字符串可以获得一个不等关系（或者无法获得），如：

ZXY
ZXW

可以知道Y < W

按照此种方法依次两两比较，可以获得多个不等关系。

当有了不等关系之后，下一步是如何根据不等关系得到这些字符的Order。最有效的方法是拓扑排序（Topology Sort）：首先对于每个不等关系，构造出图的一条边，比如Y < W可以构造出一条边，从W到Y。这样，当整个图构造完毕的时候，出度为0的就是最小的字母，然后去掉这个字母的结点及上面的所有边，再次获得出度为0的字母，这将是第二小的字母，依此类推可以获得所有字母的顺序。

这道题有两个地方需要注意：

1. 有可能输入只有单个由单个字母组成的字符串，根据定义这种情况下也是合法的，如AAAAA，结果为A。这种情况需要加以特殊处理。
2. 在构造不等关系的时候可能会遇到重复的不等关系，这个时候需要跳过，避免重复处理。（我就因为这个郁闷了好半天，一直WA）

 代码如下：

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

#define MAX 30

void compare_str( const char *a, const char *b, int adj[MAX][MAX], int degree[MAX], int out_degree[MAX])
...{
    while( *a && *b && *a == *b )
    ...{
        a++;
        b++;
    }

    if( *a && *b )
    ...{
        // directed graph
        // a <---- b ( a < b )
        int alpha_a = *a - 'A';
        int alpha_b = *b - 'A';
        if( adj[alpha_b][alpha_a] == 0 )
        ...{
            adj[alpha_b][alpha_a] = 1;
            degree[alpha_a]++;
            degree[alpha_b]++;
            out_degree[alpha_b]++;
        }
    }
}

void topo_print( int adj[MAX][MAX], int degree[MAX], int out_degree[MAX] )
...{
    int alphabets[MAX];
    int alphabets_max = 0;

    for( int i = 0; i < MAX; ++i )
    ...{
        if( degree[i] )
        ...{
            alphabets[alphabets_max++] = i;
        }
    }

    // print in topo order
    for( int i = 0; i < alphabets_max; ++i )
    ...{
        
        int alpha = -1;
        for( int j = 0; j < alphabets_max; ++j )
        ...{
            int current_alpha = alphabets[j];
            if( out_degree[current_alpha] == 0 )
            ...{
                alpha = current_alpha;
                out_degree[current_alpha] = -1;
                putchar(alpha + 'A');
                
                break;
            }
        }

        // fix out_degree
        for( int j = 0; j < alphabets_max; ++j )
        ...{
            int current_alpha = alphabets[j];
            if( adj[current_alpha][alpha] > 0 )
            ...{
                out_degree[current_alpha]--;
                adj[current_alpha][alpha] = 0;
            }
        }
    }
}

int main(int argc, char *argv[])
...{
    int adj[MAX][MAX];    
    int out_degree[MAX];
    int degree[MAX];
    int n = 0;

    memset( adj, 0, sizeof(adj) );
    memset( out_degree, 0, sizeof(out_degree) );
    memset( degree, 0, sizeof(degree) );

    bool quit = false;

    char *prev_str = new char[255];
    char *current_str = new char[255];

    scanf("%s", prev_str);
    n++;

    while(!quit)
    ...{
        scanf("%s", current_str);
        
        if( strcmp( current_str, "#" ) == 0 )
            quit = true;
        else
        ...{
            n++;

            compare_str( prev_str, current_str, adj, degree, out_degree );

            // swap prev_str & current_str and use new current_str
            char *temp = prev_str;
            prev_str = current_str;
            current_str = temp;
        }
    }

    if( n == 1 )
        putchar(prev_str[0]);
    else
        topo_print(adj, degree, out_degree);

    putchar(' ');
    

    delete prev_str;
    delete current_str;

    return 0;
}