UVa : 872 (Ordering)



// http://uva.onlinejudge.org/external/8/872.html
// Runtime: 0.012s
// Tag: Topological sort, Recursive

#include <cstdio>
#include <cstring>
#import <algorithm>
#import <vector>

using namespace std;

char chars [20 + 5];

int charsLen;

bool avail [20 + 5];

vector <int> dependency [26 + 5];

int inDegree [26 + 5];

char currChars [20 + 5];

bool found;

void parseChars(char *input) {

    charsLen = 0;

    char *pch = strtok (input, " ");

    while ( pch != NULL ) {
        chars [charsLen++] = pch [0];
        pch = strtok (NULL, " ");
    }

}

void parseDependency(char *input) {

    for ( int i = 0; i < 31; i++ ) dependency [i].clear();

    char *pch = strtok (input, " ");

    while ( pch != NULL ) {
        inDegree [pch [2] - 'A']++;
        dependency [pch [0] - 'A'].push_back(pch [2] - 'A');
        pch = strtok (NULL, " ");
    }
}

void recur(int at) {

    if (at == charsLen) {
        printf ("%c", currChars [0]);

        for (int i = 1; i < charsLen; i++ ) {
            printf (" %c", currChars [i]);
        }

        printf ("\n");

        found = true;

        return;
    }

    for ( int i = 0; i < charsLen; i++  ) {

        char c = chars [i];

        if (avail [i] && inDegree [c - 'A'] == 0) {

            currChars [at] = c;
            avail [i] = false;
            for (int k = 0; k < dependency [c - 'A'].size(); k++ )
                inDegree [dependency [c - 'A'] [k]]--;
            recur (at + 1);
            for (int k = 0; k < dependency [c - 'A'].size(); k++ )
                inDegree [dependency [c - 'A'] [k]]++;
            avail [i] = true;

        }
    }
}

int main ()
{
    int testCases;
    scanf ("%d", &testCases);

    getchar();

    char input [1000];

    while ( testCases-- ) {

        gets(input);
        gets(input);

        parseChars(input);

        gets (input);

        memset(inDegree, 0, sizeof inDegree);

        parseDependency(input);

        sort(chars, chars + charsLen);

        memset(avail, true, sizeof avail);

        found = false;

        recur(0);

        if (!found) printf ("NO\n");

        if (testCases) printf ("\n");

    }

    return 0;
}

Critical Input

4

A B F G
A<B B<F

A B F G
A<B B<F

A H K L
H<A K<L K<H A<L

A B C
A<B C<A B<C

Critical Output

A B F G
A B G F
A G B F
G A B F

A B F G
A B G F
A G B F
G A B F

K H A L

NO

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s