拓扑排序基础 hdu1258,hdu2647

时间:2025-03-13 17:34:31

由这两题可知拓扑排序是通过“小于”关系加边建图的

hdu2647

/*
拓扑排序的原则是把“小于”看成有向边
此题反向建图即可
并且开num数组来记录每个点的应该得到的权值
*/
#include<bits/stdc++.h>
#include<queue>
using namespace std;
#define maxn 20000
struct Edge{
int to,nxt;
}edge[maxn<<];
int head[maxn],tot,n,m;
void init(){
memset(head,-,sizeof head);
tot=;
}
void addedge(int u,int v){
edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++;
}
int in[maxn],num[maxn];
int main(){
while(cin>>n>>m){
init();
memset(num,,sizeof num);
memset(in,,sizeof in);
while(m--){
int u,v;
cin>>u>>v;
addedge(v,u);
in[u]++;
} queue<int>q;
for(int i=;i<=n;i++)
if(in[i]==)
q.push(i);
int ans=,tot=;
while(!q.empty()){
tot++;
int u=q.front();
q.pop();
ans+=num[u];
for(int i=head[u];i!=-;i=edge[i].nxt){
int v=edge[i].to;
--in[v];
if(in[v]==){
num[v]=num[u]+;
q.push(v);
}
}
}
if(tot<n)puts("-1");
else printf("%d\n",ans+n*);
}
}