图论2——拓扑排序
拓扑排序：*保证无环
1：模板（若要字典序则采用优先队列）
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 #include<iostream>#include<cstring> #include<queue> int s[100010],f[100010]; int vis[100010]; using namespace std; int main() { int n,m,i,temp,flag,u,v; queue<int> q; //priority_queue<int, vector<int>, greater<int> > q; memset(s,0,sizeof(s)); memset(f,0,sizeof(f)); cin>>n>>m; for (i=1;i<=m;i++) { cin>>u>>v; s[v]++; f[u]=f[u]+v; f[v]=f[v]+u; } for (i=1;i<=n;i++) { if (s[i]==0) { q.push(i); vis[i]=1; } } flag=0; while (!q.empty()) { temp=q.front(); q.pop(); f[f[temp]]-=temp; s[f[temp]]--; //temp=q.top(); if (flag) { cout<<" "; flag=1; } cout<<temp; if (s[f[temp]]==0&&!vis[f[temp]]) { q.push(f[temp]); vis[f[temp]]=1; } } cout<<endl; return 0; } 2：建立超级汇点
即，存在多个连通块，进行字典序拓扑。先用并查集分块。exm:ZOJ - 4109
AC代码：
#include<queue> #include<cstring> #include<stdio.h> #include<iostream> #include<vector> using namespace std; int edge[2000010],next[2000010],end[1000010]; bool vis[1000010]; int ans[1000010]; int f[1000010]; int find(int m) { if (m==f[m]) return m; else return find(f[m]); } void merge(int i,int t) { int t1=find(i); int t2=find(t); if (t1==t2) return; if (t1>t2) f[t1]=t2; else f[t2]=t1; } int main() { long long t,n,m,minj,num,sum,jj,k,j,i,u,v,p; priority_queue<int, vector<int>, greater<int> > q; scanf("%lld",&t); for (k=1;k<=t;k++) { scanf("%lld%lld",&n,&m); for (i=0;i<=n;i++) { f[i]=i; vis[i]=0; end[i]=0; } for (i=1;i<=m;i++) { scanf("%lld%lld",&u,&v); merge(u,v); if (end[u]==0) { end[u]=i*2-1; edge[i*2-1]=v; next[i*2-1]=0; } else { next[i*2-1]=end[u]; edge[i*2-1]=v; end[u]=i*2-1; } if (end[v]==0) { end[v]=i*2; edge[i*2]=u; next[i*2]=0; } else { next[i*2]=end[v]; edge[i*2]=u; end[v]=i*2; } } sum=0; for (i=1;i<=n;i++) { if (i==f[i]) { sum++; ans[sum]=i; } } cout<<sum<<endl; for (i=1;i<=sum;i++) { vis[ans[i]]=1; q.push(ans[i]); } while (!q.empty()) { if (q.top()!=1) cout<<" "; cout<<q.top(); p=end[q.top()]; q.pop(); while (p!=0) { if (!vis[edge[p]]) { q.push(edge[p]); vis[edge[p]]=1; } p=next[p]; } } cout<<endl; } return 0; }
更多精彩
