1. Topological Sorting

Definition:

Let $G = (V, E)$ be a directed graph with $n$ vertices. A vertex sequence from $V$ is called a topological sequence if and only if: for any path from vertex $u$ to $v$, $u$ appears before $v$ in the sequence.

Basic Idea:

1. Select a vertex with no predecessors (in-degree 0) from the AOV network and output it.
2. Remove this vertex and all edges with this vertex as the head from the AOV network.
3. Repeat until all vertices are output or no vertex with no predecessors exists.

2. Practical Exercise

Problem Description:

Xiao Ming’s lab has $N$ computers (numbered 1 to $N$). Originally, $N-1$ data links formed a tree (exactly one path between any two computers).

After a maintenence error, an extra link created a cycle (multiple paths between some computers), causing bugs. We need to find all computers in this cycle.

Input Description:

• First line: Integer $N$ ( $1 \leq N \leq 10^5$ ).
• Next $N$ lines: Two integers $a, b$ ( $1 \leq a, b \leq N$ ), representing a data link between $a$ and $b$.

The input is guaranteed to be valid (the original tree + one extra edge, forming exact one cycle).

Output Description:

Output the cycle computers’ numbers in ascending order, separated by spaces.

DFS + Topological Sort Implemantation:

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const long long MAXN = 1e5 + 10;
vector<int> adj[MAXN]; // Adjacency list
vector<int> result;   // Stores cycle nodes
int degree[MAXN] = {0}; // Degree (in/out for undirected graph)
bool visited[MAXN] = {false};

void dfs(int node) {
    visited[node] = true;
    for (int neighbor : adj[node]) {
        degree[neighbor]--;
        if (degree[neighbor] == 1) {
            dfs(neighbor);
        }
    }
}

void solve(int n) {
    // Process all leaves (degree 1) first
    for (int i = 1; i <= n; ++i) {
        if (degree[i] == 1) {
            dfs(i);
        }
    }
    // Collect unvisited nodes (cycle nodes)
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            result.push_back(i);
        }
    }
    sort(result.begin(), result.end());
    for (int node : result) {
        cout << node << " ";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, a, b;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a >> b;
        degree[a]++;
        degree[b]++;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    solve(n);
    return 0;
}

vector::begin() and vector::end()

• begin() returns an iterator to the first element of the vector.
• end() returns an iterator to the position after the last element (non-valid for access).

BFS + Topological Sort Implementation:

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

const long long MAXN = 1e5 + 10;
vector<int> adj[MAXN]; // Adjacency list
vector<int> result;   // Stores cycle nodes
int degree[MAXN] = {0}; // Degree (in/out for undirected graph)
bool visited[MAXN] = {false};
queue<int> q; // For BFS

void bfs(int n) {
    // Enqueue all leaves (degree 1)
    for (int i = 1; i <= n; ++i) {
        if (degree[i] == 1) {
            q.push(i);
            visited[i] = true;
        }
    }
    // Process nodes in queue
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        for (int neighbor : adj[curr]) {
            degree[neighbor]--;
            if (degree[neighbor] == 1) {
                q.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
    // Collect unvisited (cycle) nodes
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            result.push_back(i);
        }
    }
    sort(result.begin(), result.end());
    for (int node : result) {
        cout << node << " ";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, a, b;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a >> b;
        degree[a]++;
        degree[b]++;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    bfs(n);
    return 0;
}