拓扑排序

使用范围

在不存在互相指向的节点的有向图中。

如何操作

入度与出度

一个点的入度记录的是指向这个点的其他节点的数量

一个点的出度记录的是这个点指向的点的数量

排序方法

1.找到这个图中所有入度为0的节点。

2.将这写节点指向的节点的入度--。

3.删除这个节点（并记录下来）。
动图：https://www.cs.usfca.edu/~galles/visualization/TopoSortIndegree.html

//本段代码摘自百度


queue<int>q;
//priority_queue<int,vector<int>,greater<int>>q;
//优先队列的话，会按照数值大小有顺序的输出
//此处为了理解，暂时就用简单队列
inttopo()
{
    for(inti=1;i<=n;i++)
    {
        if(indegree[i]==0)
        {
            q.push(i);
        }
    }
 
    int temp;
    while(!q.empty())
    {
        temp=q.front();//如果是优先队列，这里可以是top()
        printf("%d->",temp);
        q.pop();
        for(inti=1;i<=n;i++)//遍历从temp出发的每一条边，入度--
        {
            if(map[temp][i])
            {
                indegree[i]--;
                if(indegree[i]==0)q.push(i);
            }
        }
    }
}

不会vector存图可以先用邻接矩阵。

车站分级

由于停靠了x车站，级别大于x车站的车站也要停。于是推得没有停靠的车站一定小于停靠的车站。（只限于起点站到终点站的区间内，这里我卡了好久）

我们就用这一个大小关系建一个图：已知的级别较小的车站指向级别较大的车站。

入度为0的点就代表现在的已知条件下，没有点保证比它更小，所以可以用类拓扑排序的方式将这些入度为0的点全部删掉。

然后一层一层删下去

直到发现没有入度为0的点，即没有剩余的点。就输出层数。

#include<bits/stdc++.h>
using namespace std;
int tu[1005][1005];
int rudu[1005];
int ans;
bool used[1005];
int main(){
//    freopen("testdata.in","r",stdin);
    int n,m;
    cin>>n>>m;
    int tai[1005],x;
    //建图，算出入度 
    for(int i=0;i<m;i++){
        bool kao[1005];//1代表靠站，0代表不靠站 
        memset(kao,0,sizeof(kao));
        cin>>x;
        for(int j=0;j<x;j++){
            cin>>tai[j];
            kao[tai[j]]=1;
        }
        for(int j=tai[0];j<=tai[x-1];j++){//一定要在起点和终点之间啊啊啊！ 
            if(!kao[j]){
                for(int k=0;k<x;k++){
                    if(!tu[j][tai[k]]){
                        tu[j][tai[k]]=1;
                        rudu[tai[k]]++;
                    }
                }
            }
        }
    }
    int cnt=10;
    int mem[1005];
    //拓扑 
    while(cnt!=0){
        cnt=0;
        for(int i=1;i<=n;i++){
            if(rudu[i]==0&&used[i]==0){//为了不再删删过的点，用used表示已删除的点 
                mem[++cnt]=i;
                used[i]=1;
            }
        }
        
        for(int i=1;i<=cnt;i++){
            for(int j=1;j<=n;j++){
                if(tu[mem[i]][j]){
                    tu[mem[i]][j]=0;
                    rudu[j]--;
                }
            }
        }
        ans++;
    }
    
    cout<<--ans;
    return 0;
}

本文链接：http://kaispace.com.cn/index.php/archives/532/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者