6-3 拓扑排序pta

### PTA 6-3 拓扑排序题解

对于PTA平台上编号为6-3的拓扑排序题目，该类问题通常涉及有向无环图(DAG)，并要求按照某种顺序排列节点使得对于每一条有向边(u, v)，u在v之前出现。

#### 方法一：Kahn算法实现拓扑排序
此方法基于入度的概念来构建拓扑序列。初始化时将所有入度为零的顶点加入队列；每次从未处理过的结点中取出一个作为当前正在访问的结点，并将其指向的所有其他结点的入度减去1；如果某个被指针所指向的结点此时入度变为0，则也将其放入待处理集合里继续上述过程直到不存在未处理的结点了为止[^1]。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 1e5 + 5;
int n, m;
vector<int> G[MAXN];
int indegree[MAXN];

void Kahn() {
    queue<int> q;
    vector<int> topo_order;
    
    // 将所有入度为0的节点入队
    for(int i=1;i<=n;++i){
        if(indegree[i]==0)q.push(i);
    }
    
    while(!q.empty()){
        int u=q.front();q.pop();
        topo_order.push_back(u);

        for(auto& v : G[u]){
            --indegree[v];
            if(indegree[v]==0)q.push(v);   
        }        
    }

    if(topo_order.size()!=n){
        cout << "Graph has at least one cycle";
    }else{
        for(auto &node:topo_order){
            printf("%d ", node);
        }
    }
}

#### 方法二：深度优先遍历DFS实现拓扑排序
另一种常见的做法是从任意起点出发利用栈记录下反序的结果，在回溯过程中依次压入最终得到正序结果。需要注意的是当遇到已经存在于栈中的元素说明存在环路则无法完成正常的拓扑排序[^3]。

bool vis[MAXN], onStack[MAXN]; 
stack<int> stk; 

// 返回是否存在环路
bool dfs(int u){  
    vis[u]=onStack[u]=true;
    bool ret=false;
      
    for(auto& v:G[u]){     
        if(onStack[v])return true;// 存在一个环
        else if(!vis[v])
          ret|=dfs(v);
     }
          
      onStack[u]=false;
      stk.push(u);
      return ret;
}

void TopologicalSort(){
    memset(vis,false,sizeof(bool)*(n+1));
    memset(onStack,false,sizeof(bool)*(n+1));

    for(int i=1;!stk.empty()||i<=n;++i){
         if(stk.empty())for(;!ret&&i<=n&&!vis[i];++i)if(dfs(i))break;
         
         if(ret){
             puts("The graph contains a cycle.");
             break;
         }
    }

    while (!stk.empty()) { 
       printf("%d ", stk.top()); 
       stk.pop(); 
    }
}