hdu1285确定比赛名次(拓扑排序+优先队列)

传送门

第一道拓扑排序题

每次删除入度为0的点,并输出

这题要求队名小的排前面,所以要用到重载的优先队列

 #include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;//优先队列默认是值越大,优先级越高,这里重载了,升序排列
int mapp[][],in[];
void topo(int n)
{
for(int i=;i<=n;i++)
{
if(in[i]==)q.push(i);//如果顶点的入度为0,入队
}
int c=;
while(!q.empty())
{
int v=q.top();
q.pop();
if(c<n)
{
printf("%d ",v);
c++;
}else
{
printf("%d\n",v); }
for(int i=;i<=n;i++)//删除该顶点
{
if(!mapp[v][i])
{
continue;
}
in[i]--;//目标顶点的入度减1
if(!in[i])q.push(i); //目标顶点入度==0,就入队
}
}
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
memset(mapp,,sizeof(mapp));
memset(in,,sizeof(in)); for(int i=;i<m;i++)
{
int p1,p2;
scanf("%d %d",&p1,&p2);
if(mapp[p1][p2])continue;
else mapp[p1][p2]=;
in[p2]++;//入度
}
topo(n);
} return ;
}
上一篇:hdu1285 确定比赛名次(拓扑排序)


下一篇:HDU1285——确定比赛名次