拓扑排序：*保证无环
1：模板（若要字典序则采用优先队列）
#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;
}
原文链接:https://www.cnblogs.com/idyllic/p/10827501.html
如有疑问请与原作者联系
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
