Topological sorting is a fundamental graph algorithm with critical applications in determining whether a directed graph contains cycles. This technique is extensively used in build systems, course scheduling, and dependency resolution.

Problem A: Topological Sort for Directed Acyclic Graphs

The core challenge involves producing a valid topological ordering by processing vertices with zero in-degree. The implementation must adhere to the specific requirements outlined in the problem statement—using a stack-based approach rather than a queue-based method.

Implementation

#include <cstdio>
#include <vector>
#include <stack>

const int MAX_VERTICES = 55;

std::vector<int> graph[MAX_VERTICES];
std::vector<int> result;
int vertexCount;
int inDegree[MAX_VERTICES];

bool computeTopologicalOrder() {
    std::stack<int> st;
    int processed = 0;
    
    for (int i = 0; i < vertexCount; ++i) {
        if (inDegree[i] == 0) {
            st.push(i);
        }
    }
    
    while (!st.empty()) {
        int current = st.top();
        st.pop();
        
        result.push_back(current);
        ++processed;
        
        for (int neighbor : graph[current]) {
            --inDegree[neighbor];
            if (inDegree[neighbor] == 0) {
                st.push(neighbor);
            }
        }
    }
    
    return processed == vertexCount;
}

int main() {
    int inputValue;
    scanf("%d", &vertexCount);
    
    for (int i = 0; i < vertexCount; ++i) {
        for (int j = 0; j < vertexCount; ++j) {
            scanf("%d", &inputValue);
            if (inputValue == 1) {
                graph[i].push_back(j);
                ++inDegree[j];
            }
        }
    }
    
    if (computeTopologicalOrder()) {
        for (size_t i = 0; i < result.size(); ++i) {
            printf("%d ", result[i]);
        }
        printf("\n");
    } else {
        printf("ERROR\n");
    }
    
    return 0;
}

Problem B: Competision Ranking Determination

This problem requires generating a valid ranking sequence where smaller-indexed teams appear first when multiple valid orderings exist. A min-heap priority queue ensures vertices with lower indices are processed first during tie-breaking scenarios.

Implementation

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

const int MAX_TEAMS = 505;

struct TeamGraph {
    std::vector<int> edges[MAX_TEAMS];
    int indegree[MAX_TEAMS];
    std::vector<int> ranking;
    int teamCount;
    
    void reset(int n) {
        teamCount = n;
        memset(indegree, 0, sizeof(indegree));
        ranking.clear();
        for (int i = 1; i <= n; ++i) {
            edges[i].clear();
        }
    }
    
    void addRelationship(int winner, int loser) {
        edges[winner].push_back(loser);
        ++indegree[loser];
    }
    
    bool generateRanking() {
        int processed = 0;
        std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
        
        for (int i = 1; i <= teamCount; ++i) {
            if (indegree[i] == 0) {
                pq.push(i);
            }
        }
        
        while (!pq.empty()) {
            int current = pq.top();
            pq.pop();
            
            ranking.push_back(current);
            ++processed;
            
            for (int competitor : edges[current]) {
                --indgree[competitor];
                if (indegree[competitor] == 0) {
                    pq.push(competitor);
                }
            }
        }
        
        return processed == teamCount;
    }
    
    void printRanking() {
        for (size_t i = 0; i < ranking.size(); ++i) {
            printf("%d", ranking[i]);
            if (i < ranking.size() - 1) {
                printf(" ");
            } else {
                printf("\n");
            }
        }
    }
};

int main() {
    int matchCount, teamA, teamB;
    TeamGraph tournament;
    
    while (scanf("%d%d", &tournament.teamCount, &matchCount) && tournament.teamCount) {
        tournament.reset(tournament.teamCount);
        
        for (int i = 0; i < matchCount; ++i) {
            scanf("%d%d", &teamA, &teamB);
            tournament.addRelationship(teamA, teamB);
        }
        
        if (tournament.generateRanking()) {
            tournament.printRanking();
        }
    }
    
    return 0;
}

Key Implementation Details

The stack-based topological sort produces a different vertex ordering compared to queue-based implementations due to LIFO versus FIFO behavior. While both approaches yield valid topological orderings, the problem specification must be carefully followed.

For competition ranking problems, the priority queue with std::greater<int> comparator ensures smaller team indices are processed first when multiple teams share the same in-degree, satisfying the lexicographic ordering requirement.

The algorithm maintains an in-degree array tracking the number of incoming edges for each vertex. Vertices with zero in-degree are candidates for processing, and their removal may cause dependent vertices to become zero in-degree, continuing the process until all vertices are processed or a cycle is detected.