拓扑排序
程序员文章站
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");
}
}