图论2——拓扑排序

拓扑排序：*保证无环 

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;

}