HDU 1285 确定比赛名次(拓扑排序&&优先队列优化)

       拓扑排序最主要的就是依靠入度进行排序，至于入度是什么，这是一个传送门 点开看看就好了。以这道题为例，裁判不知道队伍的成绩，只知道胜负，自然获胜的越多就越靠前，那么我们需要开一个二维数组来记录谁打败了谁，代码中我用了w表示win，l表示lose，那么vis[w][l]就表示w打败了l，把这个标记为1，说明他们两个比过了，然后我们还需要一个数组来记录入度，既然l输了那么就让dep[l]++，表示l的入度+了1，然后我们按入度从小到大进行输出就好了，因为题目中说明了输入的数据确保是正确的且只有一种答案，所以我们就不需要考虑如果a赢了b，b赢了c，c赢了a等等其他的乱七八糟的情况了。大概思路就是这样，具体怎么实现看代码吧。

AC代码：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 505;
bool vis[MAXN][MAXN];        // 用于标记谁打败了谁
int dep[MAXN];               // 存入度
int w,l;                     // win\lose
int n,m;

void TopoSort(int n){
  int flag;
  for(int i=1;i<=n;i++){    // 因为编号为1-n
    for(int j=1;j<=n;j++){
      if(dep[j] == 0){      // 找到入度为0的点
        printf("%d%c",j,i == n? '\n' : ' ');     // 输出
        flag = j;           // 标记这个点
        dep[j]--;           // 将其入度-1
        break;              // 跳出循环进入下一个循环
      }
    }
    for(int j=1;j<=n;j++){  // 寻找被flag打败的点
      if(vis[flag][j]){     // 如果flag把j打败了
        vis[flag][j] = false;   // 标记找到过
        dep[j]--;           // j入度-1
      }
    }
  }
}

int main()
{
  while(~scanf("%d%d",&n,&m)){
    memset(vis,0,sizeof(vis));    // 初始化
    memset(dep,0,sizeof(dep));
    for(int i=0;i<m;i++){
      scanf("%d%d",&w,&l);
      if(!vis[w][l]){         // 查重
        vis[w][l] = true;     // 标记w赢了l
        dep[l]++;             // 失败者l的入度+1
      }
    }
    TopoSort(n);
  }
  return 0;
}
/***
   [来源] HDU 1285
   [题目] 确定比赛名次
   [思路]
      拓扑排序基础题
   [输入]
      4 3
      1 2
      2 3
      4 3
   [输出]
      1 2 4 3
*/

      这样写时间复杂度会有点高，所以我们可以对拓扑排序用优先队列进行优化。

AC代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int MAXN = 505;
bool vis[MAXN][MAXN];        // 用于标记谁打败了谁
int dep[MAXN];               // 存入度
int w,l;                     // win\lose
int n,m;
priority_queue<int,vector<int>,greater<int> > q;       // 优先队列 从小到大排序

void TopoSort(int n){
  for(int i=1;i<=n;i++){     // 遍历 入度为0的入队
    if(dep[i]==0){
      q.push(i);
    }
  }
  int temp = 1;             // 标记输出结果后面是否输出空格
  while(!q.empty()){
    int ans = q.top();
    q.pop();
    if(temp != n){printf("%d ",ans);temp++;}
    else printf("%d\n",ans);
    for(int i=1;i<=n;i++){    // 找被ans打败的点
      if(vis[ans][i]){
        if(--dep[i]==0){     // 找到后先将其入度-1  如果-1后入度为0将其入队
          q.push(i);
        }
      }
    }
  }
}

int main()
{
  while(~scanf("%d%d",&n,&m)){
    memset(vis,0,sizeof(vis));
    memset(dep,0,sizeof(dep));
    for(int i=0;i<m;i++){
      scanf("%d%d",&w,&l);
      if(!vis[w][l]){
        vis[w][l] = true;
        dep[l]++;
      }
    }
    TopoSort(n);
  }
  return 0;
}