首页 > 试题广场 >

比赛名次

[编程题]比赛名次

热度指数：3105 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

输入描述:

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。

输出描述:

给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。
其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

示例1

输入

输出

1 2 4 3

算法知识视频讲解

Java

pein531

拓扑排序求解，但为了保证在有多个入度为0的队伍时，编号小的队伍能够排在前面，在实现拓扑排序时的队列应该用小根堆（系统默认的优先队列）。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.HashMap;
import java.util.PriorityQueue;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null){
            String[] params = line.split(" ");
            int n = Integer.parseInt(params[0]);
            int m = Integer.parseInt(params[1]);
            // 图的邻接表
            HashMap<Integer, LinkedList<Integer>> graph = new HashMap<>();
            // 入度表
            int[] inDegree = new int[n + 1];
            for(int i = 0; i < m; i++){
                params = br.readLine().trim().split(" ");
                int p1 = Integer.parseInt(params[0]), p2 = Integer.parseInt(params[1]);
                inDegree[p2]++;
                if(graph.containsKey(p1)){
                    graph.get(p1).add(p2);
                }else{
                    LinkedList<Integer> neighbors = new LinkedList<>();
                    neighbors.add(p2);
                    graph.put(p1, neighbors);
                }
            }
            // 找到没有入度的队伍作为起点
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            for(int i = 1; i <= n; i++){
                if(inDegree[i] == 0){
                    queue.offer(i);
                }
            }
            // 拓扑排序
            String rank = topologicalSort(graph, queue, inDegree);
            System.out.println(rank);
        }
    }
    
    private static String topologicalSort(HashMap<Integer, LinkedList<Integer>> graph, PriorityQueue<Integer> queue, int[] inDegree) {
        StringBuilder path = new StringBuilder();
        // 拓扑排序
        while(!queue.isEmpty()){
            int cur = queue.poll();
            path.append(cur).append(" ");
            if(graph.containsKey(cur)){
                Iterator<Integer> neighbors = graph.get(cur).iterator();
                while(neighbors.hasNext()){
                    int next = neighbors.next();
                    inDegree[next]--;
                    if(inDegree[next] == 0){
                        queue.offer(next);
                    }
                }
            }
        }
        return path.toString().trim();
    }
}

发表于 2022-01-06 11:01:11 回复(0)