toposort.cpp

acm 常用算法和代码库

/****************************************

* 相关变量：
* in[i] 标号为i的顶点的入度
* edge[i][j] 临接矩阵，标记i是否有指向j的有向边

by c4pt0r

****************************************/

#include <iostream>
#define MAX 100
using namespace std;
int edge[MAX][MAX]={0};
int n,e;
int in[MAX]={0};
bool topologySort()     //判断是否是dag，打印topo序 
{
        bool inStack[MAX] = {false};
        int stack[MAX], top = 0;
        int i;       
        for(i = 0; i < n; i++) {
                if(in[i] == 0) {    
                        stack[top++] = i;
                        inStack[i] = true;
                        
                }
        }
        while(top > 0) {    
                int p = stack[--top];
                cout<<p+1<<" ";           //打印topo序 
                
                for(i = 0; i < n; i++) {  //将没有入度的节点和它相连的节点的入度减一  
                        if(edge[p][i]) {
                                in[i]--;
                        }
                }
                for(i = 0; i < n; i++) {  //再次扫描，发现有入度为0 的节点，入栈 
                        if(in[i] == 0 && !inStack[i]) {
                                stack[top++] = i;
                                inStack[i] = true;
                        }
                }
        }        
        for(i = 0; i < n; i++) {
                if(!inStack[i]) {
                        return false;
                }
        }
        return true; 
}

int main()
{
    cin>>n>>e;  //节点数，边数 
    for(int i=0;i<e;i++)  //输入每条边 
    {
            int x,y;
            cin>>x>>y;   // 起始节点，结束节点 
            x--,y--;
            edge[x][y]=1;
            in[y]++;     //记录入度 
    }
    topologySort();
    system("pause");
}