欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

拓扑排序

程序员文章站 2023-12-23 17:11:22
...

参考:拓扑排序和并查集

在图论中,拓扑排序是一个有向无环图(DAG)的所有顶点的线性序列。通常,一个有向无环图可以有一个或多个拓扑排序序列。

一个有向无环图的拓扑排序:(直接看实例)
拓扑排序
怎么用代码实现:从上图中可以看出,拓扑排序每次输出的都是没有其他节点指向它的结点,即入度为0的点,所以我们将每个点的入度都记录下来,每次输出入度为0的点就可以了,同时将这个点所指的点的入度减一

记录入度:

vector<int>a[600];//存边

memset(c,0,sizeof(c));
for(int i=1; i<=n; i++)
{
    scanf("%d%d",&p1,&p2);
    a[p1].push_back(p2);
    c[p2]++;//记录入度
}

例题1:确定比赛名次
主要是题目中要求每次都是输出编号最小的队伍,可以直接遍历找编号最小的且入度为0的点,也可以借用优先队列

用邻接矩阵存边:
一开始就卡在第20行——if(!mp[p1][p2])——了,不过一条边可以输入两次!?????

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
const int maxn=510;
const int INF=0x3f3f3f3f;
priority_queue<int,vector<int>,greater<int> >qu;
int main()
{
    int n,m,c[600],p1,p2,mp[600][600];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(c,0,sizeof(c));
        memset(mp,0,sizeof(mp));
        int flag=n;
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&p1,&p2);
            if(!mp[p1][p2])
            {
                mp[p1][p2]=1;
                c[p2]++;
            }
        }
        for(int i=1; i<=n; i++)
        {
            if(!c[i])
                qu.push(i);
        }
        while(flag--)
        {
            int net=qu.top();
            qu.pop();
            if(flag)
                printf("%d ",net);
            else
                printf("%d\n",net);
            for(int j=1; j<=n; j++)
                if(mp[net][j]==1)
                {
                    c[j]--;
                    if(!c[j])
                        qu.push(j);
                }
        }
    }
}

也可以用vector和邻接表存/黑脸
例题2:Reward

//存个反向边就行了,剩下的就是套模板
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
using namespace std;
const int manx=4e4+10;
const int INF=0x3f3f3f3f;
int n,m,c[manx],head[manx],cou,a[manx];
struct node
{
    int e,bf;
} edge[manx];
void add(int s,int e)
{
    edge[cou]=node{e,head[s]};
    head[s]=cou++;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        cou=0;
        queue<int>qu;
        int s,e,ans=0,flag=n;
        memset(head,-1,sizeof(head));
        memset(c,0,sizeof(c));
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&e,&s);
            add(s,e);
            c[e]++;
        }
        for(int i=1; i<=n; i++)
            if(!c[i])
            {
                a[i]=888;
                ans+=a[i];
                qu.push(i);
                flag--;
            }
        while(!qu.empty())
        {
            int sx=qu.front();
            qu.pop();
            for(int i=head[sx]; ~i; i=edge[i].bf)
            {
                int nx=edge[i].e;
                c[nx]--;
                if(!c[nx])
                {
                    a[nx]=a[sx]+1;
                    ans+=a[nx];
                    qu.push(nx);
                    flag--;
                }
            }
        }
        if(!flag)
            printf("%d\n",ans);
        else
            printf("-1\n");
    }

}

上一篇:

下一篇: