确定比赛名次(拓扑排序 +有限对列)
确定比赛名次(拓扑排序 +有限对列)
1944864971 发表于2年前
确定比赛名次(拓扑排序 +有限对列)
  • 发表于 2年前
  • 阅读 4
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

/**
优先队列加拓扑排序
*/

include

include

include

include

using namespace std;
vector edge[500*500];
int du[550];
void creatLinJieBiao(int x,int y)
{

edge[x].push_back(y);
du[y]++;

}
struct myComp///不是结构体时 定义优先队列的方法
{
bool operator ()(int a,int b)///小的优先出队
{
return a>b;
}
};
void topSort(int n)
{
priority_queue ,myComp>q;///不是结构体的优先队列
for(int i=1; i<=n; i++)
{
if(du[i]==0)
q.push(i);
}
int op=0;
while(!q.empty())
{

    int a=q.top();
    q.pop();
    if(op==0)
        printf("%d",a);
    else printf(" %d",a);
    op=1;
    for(int i=0; i<edge[a].size(); i++)
    {
        du[edge[a][i]]--;
        if(du[edge[a][i]]==0)
        {
            q.push(edge[a][i]);
        }
    }
}
printf("\n");

}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
memset(du,0,sizeof(du));
memset(edge,0,sizeof(edge));///注意初始化
for(int i=1; i<=m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
creatLinJieBiao(x,y);
}
topSort(n);
}
return 0;
}

/**
5 5

3 4
1 5 2 3
5 4 1 2
*/

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: