是什么

有向图中,对所有的节点进行排序,要求没有一个节点指向它前面的节点。


怎么做

步骤

  1. 遍历到所有入度为0的节点,加入队列;如果没有这样的点,说明有向图构成环,则该图无解,结束算法
  2. 找到与第1步找到的相邻节点,相邻节点入度-1
  3. 元素出队,执行第1步
  4. 所有节点入度都为0后,结束算法

模板

	queue<int>q;
    for(int i=0;i<n;i++){//n:节点的总数
        if(in[i]==0){
			q.push(i);
		}
	} //将入度为0的节入队
    vector<int>ans;//ans:为拓扑序列
    while(!q.empty()){
        int p=q.top();
		q.pop();//选一个入度为0的节点出队
        ans.push_back(p);
        for(int i=0;i<edge[p].size();i++){
            int y=edge[p][i];
            in[y]--;
            if(in[y]==0){
                q.push(y);
            }
        }
    }
    if(ans.size()==n){
        for(int i=0;i<ans.size();i++){
        	cout<<ans[i];
		}
        cout<<endl;
    }else{
		cout<<"No Answer!"<<endl;//ans中的长度与n不相等,就说明无解
	}

例题

洛谷P1038 神经网络
洛谷P1113 杂务
洛谷P1137 旅行计划
洛谷P1983 车站分级
洛谷P3243 [HNOI2015]菜肴制作
洛谷P4017 最大食物链计数

12-13 03:17
查看更多