SPFA,dijskra,prime,topu四种算法的模板

时间:2022-06-02 19:38:34
 ////#include<stdio.h>
////#include<string.h>
////#include<queue>
////#include<algorithm>
////using namespace std;
////const int INF=0x3f3f3f3f;
////const int MAXN=110;
////const int MAXM=20010;
////int top,vis[MAXN],dis[MAXN],head[MAXM];
////int N,M;
////queue<int>dl;
////struct Edge{
//// int from,to,value,next;
//// };
//// Edge edg[MAXM];
////void initial(){
//// top=0;
//// memset(vis,0,sizeof(vis));
//// memset(dis,INF,sizeof(dis));
//// memset(head,-1,sizeof(head));
//// while(!dl.empty())dl.pop();
////}
////void add(int u,int v,int value){
//// Edge E={u,v,value,head[u]};
//// edg[top]=E;
//// head[u]=top++;
////}
////void SPFA(int sx){
//// dl.push(sx);
//// dis[sx]=0;
//// vis[sx]=1;
//// while(!dl.empty()){
//// int u=dl.front();
//// dl.pop();
//// vis[u]=0;
//// for(int i=head[u];i!=-1;i=edg[i].next){
//// int v=edg[i].to;
//// if(dis[u]+edg[i].value<dis[v]){
//// dis[v]=dis[u]+edg[i].value;
//// if(!vis[v]){
//// vis[v]=1;
//// dl.push(v);
//// }
//// }
//// }
//// }
//// printf("%d\n",dis[N]);
////}
////int main(){
//// int a,b,c;
//// while(~scanf("%d%d",&N,&M),N|M){
//// initial();
//// while(M--){
//// scanf("%d%d%d",&a,&b,&c);
//// add(a,b,c);
//// add(b,a,c);
//// }
//// SPFA(1);
//// }
//// return 0;
////}
///**********************************************/
//#include<stdio.h>
//#include<string.h>
//const int MAXN=110;
//const int INF=0x3f3f3f3f;
//int map[MAXN][MAXN],vis[MAXN],dis[MAXN];
//int N,M;
//void initial(){
// memset(map,INF,sizeof(map));
// memset(vis,0,sizeof(vis));
// memset(dis,INF,sizeof(dis));
//}
//void dijskra(int sx){
// dis[sx]=0;
// while(true){
// int k=-1;
// for(int i=1;i<=N;i++)
// if(!vis[i]&&(k==-1||dis[i]<dis[k]))k=i;
// if(k==-1)break;
// vis[k]=1;
// for(int i=1;i<=N;i++)
// if(!vis[i]&&dis[k]+map[k][i]<dis[i])
// dis[i]=dis[k]+map[k][i];
// }
// printf("%d\n",dis[N]);
//}
//void add(){
// int a,b,c;
// while(M--){
// scanf("%d%d%d",&a,&b,&c);
// map[a][b]=map[b][a]=c;
// }
//}
//int main(){
// while(~scanf("%d%d",&N,&M),N|M){
// initial();
// add();
// dijskra(1);
// }
// return 0;
//}
///**********************************************/
//#include<stdio.h>
//#include<string.h>
//const int MAXN=10010;
//const int INF=0x3f3f3f3f;
//int N,M,ans,flot;
//int vis[MAXN],dis[MAXN],map[MAXN][MAXN];
//void initial(){
// memset(vis,0,sizeof(vis));
// memset(dis,0x3f,sizeof(dis));
// memset(map,0x3f,sizeof(map));
// ans=0;
// flot=1;
//}
//void prime(){
// vis[1]=1;
// for(int i=1;i<=N;i++)dis[i]=map[1][i];
// while(true){
// int temp=INF,k;
// for(int i=1;i<=N;i++)
// if(!vis[i]&&dis[i]<temp)temp=dis[k=i];
// if(temp==INF)break;
// vis[k]=1;
// flot++;
// ans+=temp;
// for(int i=1;i<=N;i++)
// if(!vis[i]&&map[k][i]<dis[i])dis[i]=map[k][i];
// }
// printf("%d %d\n",ans,flot);
//}
//void add(){
// while(M--){int a,b,c;
// scanf("%d%d%d",&a,&b,&c);
// map[a][b]=map[b][a]=c;
// }
//}
//int main(){
// while(~scanf("%d%d",&N,&M),N|M){
// initial();
// add();
// prime();
// }
// return 0;
//}
/*********************************************/
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int MAXN=;
const int MAXM=;
int head[MAXM];
struct Edge{
int frome,to,next;
};
Edge edg[MAXM];
int N,M;
int que[MAXN],ans[MAXN],top,edgnum;
priority_queue<int,vector<int>,greater<int> >dl; void initial(){
memset(head,-,sizeof(head));
while(!dl.empty())dl.pop();
memset(que,,sizeof(que));
top=;edgnum=;
}
void topu(){
for(int i=;i<=N;i++)
if(!que[i])dl.push(i);
while(!dl.empty()){
int k=dl.top();
dl.pop();
ans[top++]=k;
for(int i=head[k];i!=-;i=edg[i].next){
que[edg[i].to]--;
if(que[edg[i].to]==)dl.push(edg[i].to);
}
}
for(int i=;i<top;i++)printf("%d ",ans[i]);puts("");
}
void add(int a,int b){
Edge E={a,b,head[a]};
edg[edgnum]=E;
head[a]=edgnum++;
}
void get(){
int a,b;
while(M--){
scanf("%d%d",&a,&b);
que[b]++;
add(a,b);
}
}
int main(){
while(~scanf("%d%d",&N,&M),N|M){
initial();
get();
topu();
}
return ;
}