Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 17036 Accepted Submission(s):
6747
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int s[510];
int n,m;
int map[510][510];
int vis[510];
void init()
{
int i,j,a,b;
memset(vis,0,sizeof(vis));
memset(map,0,sizeof(map));
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
if(!map[a][b])
{
vis[b]++;//连接b的边的条数
map[a][b]=1;//标记a b已经连接
}
}
}
void topu()
{
int i,j,ans=0;
priority_queue<int,vector<int>,greater<int> >q;
while(!q.empty())//清空队列
q.pop();
for(i=1;i<=n;i++)
{
if(vis[i]==0)
q.push(i); //将 没有依赖顶点的节点入队
}
int u;
while(!q.empty())
{
u=q.top();
s[ans++]=u;//将上边选出的没有依赖顶点的节点加入到排序结果中
q.pop();//删除队顶元素
for(i=1;i<=n;i++)
{
if(map[u][i])
{
vis[i]--;//删去以u为顶点的边
if(vis[i]==0)//如果节点i的所有依赖顶点连接边都已经删去
q.push(i);//即变为无依赖顶点的节点 将其入队
}
}
if(ans==n)
{
for(i=0;i<ans;i++)
{
if(i==0)
printf("%d",s[i]);
else
printf(" %d",s[i]);
}
printf("\n");
}
}
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
topu();
}
return 0;
}
原文:http://www.cnblogs.com/tonghao/p/4721022.html