Topological Sort - Algorithm and Problems

Algorithm Explanation

Topological sorting is applicable only to Directed Acyclic Graphs (DAGs). It orders vertices such that for every directed edge u → v, vertex u comes before v in the ordering.

Approach (Kahn's Algorithm - BFS Based)

1. Compute in-degree for each node.
2. Initialize a queue with all nodes having in-degree 0.
3. While the queue is not empty:
   • Pop a node from the queue and add it to the result.
   • Decrease in-degree of its neighbors. If in-degree becomes 0, add to queue.

Time Complexity

O(V + E) where V = number of vertices, E = number of edges.

Memory Complexity

O(V + E) for adjacency list and auxiliary structures like in-degree and queue.

Easy Problems

1. Course Schedule

Given prerequisites, determine if all courses can be finished.

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses);
    vector<int> in_degree(numCourses, 0);
    for (auto p : prerequisites) {
        graph[p[1]].push_back(p[0]);
        in_degree[p[0]]++;
    }
    queue<int> q;
    for (int i = 0; i < numCourses; ++i)
        if (in_degree[i] == 0) q.push(i);

    int count = 0;
    while (!q.empty()) {
        int node = q.front(); q.pop(); count++;
        for (int neighbor : graph[node])
            if (--in_degree[neighbor] == 0) q.push(neighbor);
    }
    return count == numCourses;
}

2. Task Ordering

Return one valid order of tasks given dependency rules.

vector<int> findOrder(int numTasks, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numTasks);
    vector<int> in_degree(numTasks, 0);
    for (auto &p : prerequisites) {
        graph[p[1]].push_back(p[0]);
        in_degree[p[0]]++;
    }
    queue<int> q;
    for (int i = 0; i < numTasks; ++i)
        if (in_degree[i] == 0) q.push(i);

    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : graph[u])
            if (--in_degree[v] == 0) q.push(v);
    }
    return (order.size() == numTasks) ? order : vector<int>();
}

Intermediate Problems

1. Alien Dictionary

Determine the order of characters in an alien language.

string alienOrder(vector<string>& words) {
    unordered_map<char, unordered_set<char>> graph;
    unordered_map<char, int> in_degree;
    for (string word : words)
        for (char c : word) in_degree[c] = 0;

    for (int i = 0; i < words.size() - 1; ++i) {
        string w1 = words[i], w2 = words[i + 1];
        int len = min(w1.size(), w2.size());
        for (int j = 0; j < len; ++j) {
            if (w1[j] != w2[j]) {
                if (!graph[w1[j]].count(w2[j])) {
                    graph[w1[j]].insert(w2[j]);
                    in_degree[w2[j]]++;
                }
                break;
            }
        }
    }
    queue<char> q;
    for (auto &[c, deg] : in_degree)
        if (deg == 0) q.push(c);

    string result;
    while (!q.empty()) {
        char c = q.front(); q.pop();
        result += c;
        for (char nei : graph[c])
            if (--in_degree[nei] == 0) q.push(nei);
    }
    return (result.size() == in_degree.size()) ? result : "";
}

2. Build System Dependency

Given file dependencies, output build order.

vector<string> buildOrder(vector<pair<string, string>>& dependencies) {
    unordered_map<string, vector<string>> graph;
    unordered_map<string, int> in_degree;
    for (auto &dep : dependencies) {
        graph[dep.second].push_back(dep.first);
        in_degree[dep.first]++;
        if (!in_degree.count(dep.second)) in_degree[dep.second] = 0;
    }
    queue<string> q;
    for (auto &[node, deg] : in_degree)
        if (deg == 0) q.push(node);

    vector<string> order;
    while (!q.empty()) {
        string node = q.front(); q.pop();
        order.push_back(node);
        for (string &nei : graph[node])
            if (--in_degree[nei] == 0) q.push(nei);
    }
    return (order.size() == in_degree.size()) ? order : vector<string>();
}

Hard Problem

1. Minimum Time to Complete All Tasks

Each task has duration and dependencies. Find minimum total time.

int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
    vector<vector<int>> graph(n);
    vector<int> in_degree(n, 0), dp(n);
    for (auto &r : relations) {
        graph[r[0] - 1].push_back(r[1] - 1);
        in_degree[r[1] - 1]++;
    }
    queue<int> q;
    for (int i = 0; i < n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
            dp[i] = time[i];
        }
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : graph[u]) {
            dp[v] = max(dp[v], dp[u] + time[v]);
            if (--in_degree[v] == 0) q.push(v);
        }
    }
    return *max_element(dp.begin(), dp.end());
}