首页 > 试题广场 >

比赛名次

[编程题]比赛名次
  • 热度指数：3095 时间限制：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

输入

4 3
1 2
2 3
4 3

输出

1 2 4 3
算法知识视频讲解
添加回答
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    while(cin>>n>>m){
        vector<int> Edge[n+1];
        int inDegree[n+1];
        memset(inDegree,0,sizeof(inDegree));
        for(int i=0;i<m;i++){
            int a,b;
            cin>>a>>b;
            Edge[a].push_back(b);
            inDegree[b]++;
        }
        priority_queue<int, vector<int>, greater<int>> Q;
        for(int i=1;i<=n;i++)
            if(inDegree[i]==0)
                Q.push(i);

        int cnt = 1;
        while(!Q.empty()){
            int u = Q.top();
            Q.pop();
            if(cnt==n)
                cout<<u<<endl;
            else
                cout<<u<<" ";
            cnt++;
            for(int i=0;i<Edge[u].size();i++){
                int v = Edge[u][i];
                inDegree[v]--;
                if(inDegree[v]==0)
                    Q.push(v);
            }
        }
    }
    return 0;
}

发表于 2019-07-17 01:05:06 回复(1)
lentolove头像 lentolove 
import java.io.*;
import java.util.*;


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while ((str = bf.readLine()) != null) {
            String[] line1 = str.split(" ");
            int n = Integer.parseInt(line1[0]);//队伍的个数
            int m = Integer.parseInt(line1[1]);//总共有m场比赛
            //记录n个队伍比赛输掉的次数
            int[] num1 = new int[n + 1];
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            //记录第i个队伍赢得的队伍
            HashMap<Integer, ArrayList<Integer>> map = new HashMap<>(m);
            int a, b;
            for (int i = 1; i <= m; i++) {
                line1 = bf.readLine().split(" ");
                a = Integer.parseInt(line1[0]);//赢比赛的队伍
                b = Integer.parseInt(line1[1]);//输比赛的队伍
                if (!map.containsKey(a)) {
                    map.put(a, new ArrayList<>());
                }
                map.get(a).add(b);
                //eg：b队伍输的次数加一
                num1[b]++;
            }
            for (int i = 1; i <= n; i++) {//将那些没有输过比赛的队伍加到优先队列中,题目要求相同排名的编号小的放在前面
                if (num1[i] == 0) queue.add(i);
            }
            //保存输出结果
            StringBuilder sb = new StringBuilder();
            while (!queue.isEmpty()) {
                int top = queue.poll();
                sb.append(top);
                sb.append(" ");
                for (int i = 0; map.containsKey(top) && i < map.get(top).size(); i++) {
                    int x = map.get(top).get(i);
                    num1[x]--;
                    if (num1[x] == 0) queue.add(x);
                }
            }
            sb.substring(0,sb.length()-1);
            System.out.println(sb.toString());
        }
    }
}
发表于 2019-07-30 10:43:23 回复(0)
Python
ElonB头像 ElonB 
""""
每次找到在第一列且不在第二列，或没有比赛结果的队伍，
输出最小编号，删除包含此最小编号队伍的比赛结果，重复上一步骤。
优化时间复杂度，优化比赛结果的存储格式，设置各队伍的入度(输的数量),可以用优先级队列进一步优化
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    try:
        while True:
            n, m = map(int, input().strip().split())
            edge = [[] for _ in range(n + 1)]
            indegree = [0] * (n + 1)
            for _ in range(m):
                a, b = map(int, input().strip().split())
                edge[a].append(b)
                indegree[b] += 1
            pre = []
            ans = []
            for i in range(1, n + 1):
                if indegree[i] == 0:
                    pre.append(i)
            while pre:
                ans.append(min(pre))
                pre.remove(ans[-1])
                for k in edge[ans[-1]]:
                    indegree[k] -= 1
                    if indegree[k] == 0:
                        pre.append(k)
            print(' '.join(map(str, ans)))
    except:
        pass

编辑于 2019-07-14 09:52:25 回复(0)
Java
pein531头像 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)
妖骨头像 妖骨
常规的拓扑排序，只不过此时根据题目限制条件使用了小顶堆，保证编号小的在前面。 
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> edge[501]; // 邻接链表
priority_queue<int, vector<int>, greater<int> > Q;
int ans[501];
int inDegree[501];

int main(){
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        // 初始化
        for(int i = 1; i <= n; i++){
            inDegree[i] = 0;
            edge[i].clear();
        }

        for(int i = 0; i < m; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            inDegree[b]++;
            edge[a].push_back(b);
        }
        while(Q.empty()==false) Q.pop();
        for(int i = 0; i < n; i++)
            ans[i] = 0;

        for(int i = 1; i <= n; i++){
            if(inDegree[i] == 0) Q.push(i);
        }

        int cnt = 0;
        while(Q.empty()==false){
            int node = Q.top();
            ans[cnt++] = node;
            Q.pop();
            for(int i = 0; i < edge[node].size(); i++)
            {
                inDegree[edge[node][i]]--;
                if(inDegree[edge[node][i]] == 0)
                    Q.push(edge[node][i]);
            }
        }
        for(int i = 0; i < n-1; i++)
            printf("%d ", ans[i]);
        printf("%d\n", ans[n-1]);
    }
    return 0;

}


编辑于 2020-08-29 09:30:16 回复(0)
超越姐姐保佑我i头像 超越姐姐保佑我i

拓扑排序问题。

注意：因为相同名次的情况下，编号小的在前，所以需要使用优先队列。 

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] arr = new int[m][2];
            int[] degrees = new int[n + 1];
            for(int i = 0; i < m; i ++) {
                arr[i][0] = sc.nextInt();
                arr[i][1] = sc.nextInt();
                degrees[arr[i][1]] ++; 
            }

            PriorityQueue<Integer> queue = new PriorityQueue<>();
            for(int i = 1; i <= n; i ++) {
                if(degrees[i] == 0) queue.offer(i);
            }

            List<String> res = new ArrayList<>();
            while(!queue.isEmpty()) {
                int cur = queue.poll();
                res.add(String.valueOf(cur));
                for(int[] a : arr) {
                    if(a[0] != cur) continue;
                    if(-- degrees[a[1]] == 0) queue.offer(a[1]);
                }
            }

            System.out.println(String.join(" ", res));
        }
    }
}
编辑于 2019-08-19 17:17:36 回复(0)
猫猫猫1头像 猫猫猫1
#include<bits/stdc++.h>
using namespace std;

const int Max=501;
vector<int> graph[Max];
int indegree[Max]={0};

void TopologicalSort(int n){
    vector<int> answer;
    priority_queue<int,vector<int>,greater<int> > q;
    for(int i=1;i<=n;i++){
        if(indegree[i]==0){
            q.emplace(i);
        }
    }
    while(!q.empty()){
        int u=q.top();
        answer.emplace_back(u);
        q.pop();
        for(int i=0;i<graph[u].size();i++){
            int v=graph[u][i];
            indegree[v]--;
            if(indegree[v]==0){
                q.emplace(v);
            }
        }
    }
    for(int i=0;i<answer.size();i++){
        cout<<answer[i]<<" ";
    }
    cout<<endl;
    return ;
}

int main(){
    int n,m;
    while(cin>>n>>m){
        memset(graph,0,sizeof(graph));
        while(m--){
            int x,y;
            cin>>x>>y;
            graph[x].emplace_back(y);
            indegree[y]++;
        }
        TopologicalSort(n);
    }
    return 0;
}
发表于 2022-10-14 16:53:08 回复(0)
C++
牛客407263516号头像 牛客407263516号
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN=501;

vector<int> graph[MAXN];
int indegree[MAXN];

void gsort(int n){
    priority_queue<int,vector<int>,greater<int>> myqueue;
    for(int i=1;i<=n;i++){
        if(indegree[i]==0){
            myqueue.push(i);
        }
    }
    int flag=0;
    while(!myqueue.empty()){
        int cur=myqueue.top();
        myqueue.pop();
        if(flag==0){
            cout<<cur;
            flag=1;
        }else{
            cout<<" "<<cur;
        }
        for(int i=0;i<graph[cur].size();i++){
            int node=graph[cur][i];
            indegree[node]--;
            if(indegree[node]==0){
                myqueue.push(node);
            }
        }
    }
}

int main(){
    int n,m;
    while(cin>>n>>m){
        memset(graph,0,sizeof(graph));
        memset(indegree,0,sizeof(indegree));
        if(n==0) break;
        int p1,p2;
        for(int i=0;i<m;i++){
            cin>>p1>>p2;
            graph[p1].push_back(p2);
            indegree[p2]++;
        }
        gsort(n);
        cout<<endl;
    }
}
发表于 2022-09-05 16:51:09 回复(0)
zanejins头像 zanejins 
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N=10000;
vector<int> edge[520];
priority_queue<int, vector<int>, greater<int>> Q; //小顶堆
int inDegree[N];
int n,m;
int main() {
    while(scanf("%d%d",&n,&m)!=EOF) {
        for(int i=1;i<=n;i++) {
            inDegree[i]=0;
            edge[i].clear();
        }
        while(m--) {
            int a,b;
            scanf("%d%d",&a,&b);
            inDegree[b]++;
            edge[a].push_back(b);
        }
        while(Q.empty()==false) Q.pop();
        for(int i=1;i<=n;i++) {
            if(inDegree[i]==0) Q.push(i);
        }
        int cnt=1;
        while(Q.empty()==false) {
            int nowP=Q.top();
            Q.pop();
            if(cnt==n)
                cout<<nowP<<endl;
            else
                cout<<nowP<<" ";
            cnt++;
            for(int i=0;i<edge[nowP].size();i++) {
                inDegree[edge[nowP][i]]--;
                if(inDegree[edge[nowP][i]]==0) Q.push(edge[nowP][i]);
            }
        }
    }
}

这里因为每次插入队列的时候需要按照大小进行排序，因此直接用了王道考研的模板换成了优先级队列，其他基本是不变的。但是这个题目耗费了我好长的时间，找了好长时间的bug，没想到是edge开的太小了，只开了500.改成520就对了。关于拓扑排序的模板和问题我梳理了一下，具体的博文链接如下：

发表于 2022-04-29 20:29:29 回复(0)
ambulace_头像 ambulace_

拓扑排序

根据当前节点的入度判断排名在该节点以前的点是否都已经完成排序

#include<bits/stdc++.h>
using namespace std;

vector<int> Sort(vector<vector<int>> AdjList,vector<int> &inDegree){
    vector<int> ans(AdjList.size(),0);
    priority_queue<int, vector<int>, greater<int> > Q;
    for (int i = 1; i <inDegree.size();i++){
        if (!inDegree[i])
            Q.push(i);
    }

    int cnt = 0;
    while(!Q.empty()){
        int cur = Q.top();
        Q.pop();
        cnt += 1;
        ans[cnt] = cur;
        for(auto &n:AdjList[cur]){
            inDegree[n]--;
            if(inDegree[n]==0){
                Q.push(n);
            }
        }
    }
    return ans;
}


int main(){
    int N, M;
    while (cin>>N>>M)
    {
        vector<vector<int>> AdjList;
        AdjList.resize(N + 1);
        vector<int> inDegree(N + 1,0);
        int fa, son;
        for (int i = 0; i < M;i++){
            cin >> fa >> son;
            AdjList[fa].push_back(son);
            inDegree[son] += 1;
        }

        vector<int> ans = Sort(AdjList,inDegree);
        for (int i = 1; i < ans.size()-1;i++)
        {
            cout << ans[i] << " ";
        }
        cout << ans[ans.size() - 1] << endl;
    }

    return 0;
}
发表于 2021-06-13 11:27:36 回复(0)
C/C++
毓毓子最可爱头像 毓毓子最可爱
#include<bits/stdc++.h>
using namespace std;
//拓扑排序
const int maxv=501;//最大顶点数
int inDegree[maxv]={0};//每个顶点的入度
vector<int> g[maxv];//领接表
int n,m;//顶点数，边数
int u,v;//顶点
int findZeroDegree(int n)
{
    //寻找下一个入度为0的顶点，保证了结点值最小的优先
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(inDegree[i]==0)
        {
            ans=i;
            break;
        }
    }
    return ans;
}
int main()
{
    int count;
   while(cin>>n>>m)
   {
       count=n;
       //初始化
       for(int i=1;i<=n;i++)
       inDegree[i]=0;
       for(int i=1;i<=n;i++)
       g[i].clear();
       //读入图
       for(int i=0;i<m;i++)
       {
           cin>>u>>v;
           g[u].push_back(v);
           inDegree[v]++;
       }
       //拓扑排序主体
       queue<int> q;
       q.push(findZeroDegree(n));
       int length;
       int temp;
       while(q.size()&&q.front()!=0)
       {
           temp=q.front();
           length=g[temp].size();
           q.pop();//输出顶点
           inDegree[temp]=INT_MAX;//避免下次找到
           //输出格式控制
           count--;
           if(count!=0)
           cout<<temp<<" ";
           else
           cout<<temp<<endl;
           //将连接结点入度减一
           for(int i=0;i<length;i++)
           {
               inDegree[g[temp][i]]--;
           }
           q.push(findZeroDegree(n));
       }
   }
    return 0;
}


发表于 2020-08-22 21:54:23 回复(0)
风吹不过的夏天头像 风吹不过的夏天 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500;
int indegree[maxn];
vector<int> graph[maxn];
void topologicalsort(int n){
    priority_queue<int,vector<int>,greater<int> > q;
    for(int i=1;i<=n;i++)
        if(indegree[i]==0)
            q.push(i);
    while(!q.empty()){
        int u = q.top();
        q.pop();
        cout<<u<<" ";
        for(int i=0;i<graph[u].size();i++){
            int v = graph[u][i];
            indegree[v]--;
            if(indegree[v] == 0)
                q.push(v);
        }
    }
}
int main(){
    int n,m;
    while(cin>>n>>m){
        if(n == 0 && m == 0)
            break;
        int from,to;
        memset(graph,0,sizeof(graph));
        memset(indegree,0,sizeof(indegree));
        for(int i=1;i<=m;i++){
            cin>>from>>to;
            graph[from].push_back(to);
            indegree[to]++;
        }
        topologicalsort(n);
    }
}

发表于 2020-08-16 17:38:17 回复(0)
ac_q头像 ac_q 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <functional>
using namespace std;


const int  N = 510;
int a[N];
int n,m;
int degree[N];
bool visit[N];
vector<int> v[N];

int main()
{
    while(cin >> n >> m)
    {
     
    for(int i = 0; i < m; i++)
    {
        int n = 0;
        int m = 0;
        cin >> n >> m;
        v[n].push_back(m);
        degree[m]++;
    }
   // priority_queue<int,vector<int>, greater<int>> q;
    queue<int> q;
    vector<int> res;
    vector<int> tmp;
    for(int i = 1; i <= n; i++)
    {
        if(degree[i] == 0)
        {
            q.push(i);
            visit[i] = true;
            break; //注意break;
           
        }
    }
    /*
    sort(tmp.begin(),tmp.end());
    res = tmp;
    tmp.clear();
   */
    while(q.size())
    {
        int sz = q.size();
        while(sz--)
        {
            auto tmp = q.front();
            q.pop();
            res.push_back(tmp);
            for(int i = 0; i < v[tmp].size(); i++)
            {
                degree[v[tmp][i]]--;
            }
              
        }
        for(int i = 1; i <= n; i++)
        {
            if(degree[i] == 0 && visit[i] != true)
            {
                q.push(i);
                visit[i] = true;
                break; //注意break
            }
        }
    }
    for(auto e: res)
    {
        cout << e << " " ;
    }
    cout << endl;
     memset(v,0, sizeof v);
     memset(visit,false, sizeof visit);
     memset(degree,false, sizeof degree);
    }
}

发表于 2020-07-03 20:02:48 回复(0)
C/C++
游人_渐稀l头像 游人_渐稀l 
//我只是代码的搬运工！！
#include<iostream>
(720)#include<cstring>
#include<vector>
(721)#include<queue>

using namespace std;

const int MAXN = 500 + 10;

vector<int> graph[MAXN];
int inDegree[MAXN];

vector<int> TopologicalSort(int n)
{
    vector<int> answer;
    priority_queue<int, vector<int>, greater<int> > node;
    for(int i = 1; i <= n; ++i)
    {
        if(inDegree[i] == 0)
        {
            node.push(i);
        }
    }
    while(!node.empty())
    {
        int current = node.top();
        answer.push_back(current);
        node.pop();
        for(int i = 0; i < graph[current].size(); ++i)
        {
            int temp = graph[current][i];
            inDegree[temp]--;
            if(inDegree[temp] == 0)
            {
                node.push(temp);
            }
        }
    }
    return answer;
}

int main()
{
    int n, m;
    while(cin>>n>>m)
    {
        memset(graph, 0, sizeof(graph));
        memset(inDegree, 0, sizeof(inDegree));
        while(m--)
        {
            int from, to;
            cin>>from>>to;
            graph[from].push_back(to);
            inDegree[to]++;
        }
        vector<int> answer = TopologicalSort(n);
        for(int i = 0; i < answer.size(); ++i)
        {
            if(i == 0)
            {
                cout<<answer[i];
            }
            else
            {
                cout<<" "<<answer[i];
            }
        }
        cout<<endl;
    }
    return 0;
}

发表于 2020-04-28 15:56:14 回复(0)
sky游荡头像 sky游荡
拓扑排序加优先级队列。 
from collections import defaultdict
from queue import PriorityQueue

while True:
    try:
        m,n = map(int,input().split())
        qzero = PriorityQueue()
        graph = defaultdict(list)
        weight = [0]*(m+1)

        for i in range(n):
            a,b = map(int,input().split())
            weight[b] += 1
            graph[a].append(b)      
        for i in range(1,m+1):
            if weight[i]==0:
                qzero.put(i)

        ans = []
        while not qzero.empty():    
            node = qzero.get()
            ans.append(node)
            for index in graph[node]:
                    weight[index] -= 1
                    if weight[index] == 0:
                        qzero.put(index)
        ans = list(map(str,ans))
        print(' '.join(ans))
    except:
        break
 

    


发表于 2020-04-26 15:12:26 回复(0)
fusnzusi头像 fusnzusi 
#include<stdio.h>
int main(){
	int n,m;
	int res[505][505];
	int in[505];
	int ans[505];int p=0;
	while(scanf("%d%d",&n,&m)!=EOF){
		p=0;
		for(int i=0;i<505;i++){
			in[i]=0;
			for(int j=0;j<505;j++)
				res[i][j]=0;
		}
		if(n==0) break;
		for(int i=0;i<m;i++){
			int a,b;
			scanf("%d %d",&a,&b);
			res[a][b]=1;
			in[b]++;
		}
		while(1){
			int flag=0;
			for(int i=1;i<=n;i++){				
				if(in[i]==0){
					in[i]=-1;
					ans[p++]=i;
					for(int j=1;j<=n;j++){
						if(res[i][j]==1){
							in[j]--;
							flag=1;
						}
					}
				}
				if(flag==1) break; //从i=1开始
			}
			if(flag==0) break;
		}
		for(int i=0;i<n;i++){
			printf("%d ",ans[i]);
		}
		printf("\n");
	}
}

发表于 2020-04-12 18:27:19 回复(0)
C/C++
鱼香-肉丝头像 鱼香-肉丝 
#include<bits/stdc++.h>//拓扑排序
using namespace std;
vector<int>edge[501];//存储节点及后继关系
priority_queue<int,vector<int>,greater<int> >Q;//存储入度为0的点，编号由小到大
int main()
{
    int N,M;
    int inDegree[501];//统计每个节点的入度
    while(cin>>N>>M)
    {
        //初始化所有节点的入度和链接情况
        for(int i=1;i<=N;i++)
        {
            inDegree[i]=0;
            edge[i].clear();
        }
        while(M--){
            int a,b;
            cin>>a>>b;
            inDegree[b]++;
            edge[a].push_back(b);//a的后继是b
        }
        while(!Q.empty()) Q.pop();
        //将入度为0的点放入队列
        for(int i=1;i<=N;i++){
            if(inDegree[i]==0)
                Q.push(i);
        }
        //对入度为0的点进行遍历
        int cnt=0;
        while(!Q.empty())
        {
            int tmp=Q.top();//如果要求拓扑序列，就将tmp存入另一队列中
            Q.pop();
            cnt++;
            if(cnt==N) cout<<tmp<<endl;//最后一个数
            else cout<<tmp<<" ";
            for(int i=0;i<edge[tmp].size();i++)
            {
                int tmpp=edge[tmp][i];//tmp的后继节点
                inDegree[tmpp]--;
                if(inDegree[tmpp]==0)
                    Q.push(tmpp);
            }
        }
    }
    return 0;
}
发表于 2020-02-17 20:28:56 回复(0)
断肠人在天涯201812021037877头像 断肠人在天涯201812021037877
想了好久才找到好的解决办法，只记录失败次数即可
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<int, int> pii;
void get_sequence(vector<pii> data, int n, int m, vector<int>& result) {
    sort(data.begin(), data.end());
    vector<int> temp(n+1, 0);//记录失败次数
    //遍历比赛结果，分别记录胜利和失败场数，下标即为队伍编号
    for (int i = 0; i < m; i++) {
        temp[data[i].second]++;
    }
    for(int k=0; k<n; k++) {
        for (int i = 1; i < temp.size(); i++)
            if (temp[i] == 0) {
                result.push_back(i);//找到没有失败的队伍，编号加入结果
                int pos = 0;
                for (; pos < data.size(); pos++) {
                    if (data[pos].first == i) {
                        while (pos < data.size() && data[pos].first == i)
                            temp[data[pos++].second]--;//减去已入队的队伍对比赛结果的影响
                        break;
                    }
                }
                temp[i] = n;
                break;
            }
    }
}
int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<pii> data(m);
        for (int i = 0; i < m; i++)
            cin >> data[i].first >> data[i].second;
        vector<int> result;
        get_sequence(data, n, m, result);
        for (int i = 0; i < result.size() - 1; i++)
            cout << result[i] << " ";
        cout << result[result.size() - 1] << endl;
    }
    return 0;
}
发表于 2019-09-05 10:47:49 回复(0)
XII0001头像 XII0001
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
void getAns(vector<vector<int>> &edges, vector<int> &indegree){
    int n = edges.size();
    priority_queue<int, vector<int>, greater<int>> myQue;
    for(int i=0; i<n; i++) 
        if(indegree[i]==0) 
            myQue.push(i);
    while(!myQue.empty()){
        auto index = myQue.top(); myQue.pop();
        cout<<index+1<<' ';
        for(auto val : edges[index]){
            indegree[val]--;
            if(indegree[val]==0) myQue.push(val);
        }
    }
    cout<<endl;
}
int main(){
    // 拓扑排序
    int n, m;
    while(cin>>n>>m){
        vector<vector<int>> edges(n);
        vector<int> indegree(n,0);
        int x, y;
        for(int i=0; i<m; i++){
            cin>>x>>y;
            edges[x-1].push_back(y-1);
            indegree[y-1]++;
        }
        getAns(edges, indegree);
    }
    return 0;
}

发表于 2019-07-06 10:25:52 回复(0)
我的女朋友为什么这么好看头像 我的女朋友为什么这么好看
#include <stdio.h> 
#include<queue>
#include <vector> 
#include<algorithm>
#include<functional>
using namespace std; 
vector<int> edge[501];
priority_queue<int, vector<int>, greater<int>> Q;
int InDegree[501];
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) != EOF)
    {
        for (int i = 1; i <= n; i++)
        {
            edge[i].clear();
            InDegree[i] = 0;
        }
        while (m--)
        {
            int a, b;
            scanf("%d %d", &a, &b);
            InDegree[b]++;
            edge[a].push_back(b);
        }
        while (!Q.empty())
            Q.pop();
        for (int i = 1; i <= n; i++)
            if (InDegree[i] == 0)
                Q.push(i);
        while (!Q.empty())
        {
            int tmp = Q.top();
            Q.pop();
            printf("%d ", tmp);
            for (int i = 0; i < edge[tmp].size(); i++)
            {
                InDegree[edge[tmp][i]]--;
                if (InDegree[edge[tmp][i]] == 0)
                    Q.push(edge[tmp][i]);
            }
        }
        printf("\n");
    }
    return 0;
}
发表于 2019-03-14 15:28:31 回复(0)
提交观点

问题信息

运维工程师 小米集团 图 2019 安全工程师 排序
来自：小米2019秋招安全开...
上传者：小小
难度：
20条回答 6536浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号