首页 > 试题广场 >

卡中心美食家

[编程题]卡中心美食家

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

在卡中心隐藏了很多美食，作为一名资深吃货，楼主告诉你需要去品尝n道美味才能达成“卡中心小小美食家”的成就。这些菜品被标号为 0 到 n-1 。正所谓美食家不是一口吃成个胖子的，每道美味的品尝顺序也是有讲究的，比如西餐的上菜顺序：头盘，汤，副菜，主菜，蔬菜类菜肴，甜品，咖啡或茶。有一些美味需要“前置菜肴”，比如如果你要吃菜品0，你需要先吃菜品1，我们用一个范式来表示这些规则：[0 1]。接下来给你菜品的总数量n和m个“前置菜肴”的范式，请编程输出你为了品尝完所有美味所安排的进餐顺序。可能会有多个正确的顺序，你只要输出一种就可以了。如果不可能品尝完所有美味，返回None。

输入描述:

输入的第一行为以空格分隔的两个正整数，第一个表示原始美味总数n，第二个表示前置菜肴范式总数m。
其后m行每行均为一个以空格分隔的范式说明，第一列为待吃菜肴的标号，第二列为前置菜肴的标号。

输出描述:

对每组测试数据，单独输出一行答案，菜肴标号之间用英文逗号分隔。

示例1

输入

输出

只需输出以下任一种结果即可
0,1,2,3
或
0,2,1,3

算法知识视频讲解

向宇回桌

很简单的一个top排序

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m; scanf("%d %d", &n, &m);
    vector<vector<int>> tmap(n + 5);
    int *count = new int[n + 5];
    memset(count, 0, sizeof(int)*(n+5));
    for (int i=0; i<m; i++) {
        int from, to;
        scanf("%d %d", &to, &from);
        tmap[from].push_back(to);
        count[to]++;
    }
    queue<int> zeros;
    for (int i=0; i<n; i++) {
        if (count[i] == 0) {
            zeros.push(i);
        }
    }
    vector<int> ans;
    while (!zeros.empty()) {
        int now = zeros.front();
        zeros.pop();
        vector<int> &tto = tmap[now];
        for (vector<int>::iterator it = tto.begin(); it!=tto.end(); it++) {
            count[*it]--;
            if (count[*it] == 0) zeros.push(*it);
        }
        ans.push_back(now);
    }
    string out;
    if (ans.size() != n) {
        cout << "None" << endl;
    }
    else {
        for (vector<int>::iterator it = ans.begin(); it != ans.end(); it++) {
            out += to_string((*it));
            out += ",";
        }
    }
    cout << out.substr(0, out.length()-1);
    return 0;
}

发表于 2019-04-09 12:21:21 回复(2)

C/C++

nbgao

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

int main(){
    int n, m, u, v;
    scanf("%d%d", &n, &m);
    vector<int> G[n], r;
    int in[n];
    memset(in, 0, sizeof(in));
    for(int i=0;i<m;i++){
        scanf("%d%d", &u, &v);
        G[v].push_back(u);
        in[u]++;
    }
    queue<int> q;
    for(int i=0;i<n;i++)
        if(in[i]==0)
            q.push(i);
    while(!q.empty()){
        u = q.front();
        q.pop();
        r.push_back(u);
        for(auto &v: G[u])
            if(--in[v]==0)
                q.push(v);
    }
    if(r.size() < n)
        printf("None\n");
    else
        for(int i=0;i<n;i++){
            if(i==n-1)
                printf("%d\n", r[i]);
            else
                printf("%d,", r[i]);
        }
    return 0;
}

发表于 2020-10-24 13:44:46 回复(0)

chorifa

import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        int n = Integer.parseInt(strs[0]), m = Integer.parseInt(strs[1]);
        boolean[][] graph = new boolean[n][n]; // graph[i][j]代表i是否需要j
        while(m-->0){
            strs = br.readLine().split(" ");
            graph[Integer.parseInt(strs[0])][Integer.parseInt(strs[1])] = true;
        }
        int[] res = new int[n]; // 存放输出序列
        boolean[] isRecord = new boolean[n]; // 存放i是否已经在输出序列中
        int index = 0, len = 0; // index为当前索引，len为操作一次后res的实际长度
        do{
            // 更新index
            index = len;
            // 找到没有前置要求的新节点
            for(int i = 0; i < n; i++){
                if(isRecord[i]) continue;
                int tmp = 0;
                while(tmp<n){
                    if(graph[i][tmp]) break;
                    tmp++;
                }
                if(tmp == n) {res[len++] = i; isRecord[i] = true;}
            }
            // 用节点来更新图
            for(int i = index; i < len; i++)
                for(int row = 0; row < n; row++)
                    graph[row][res[i]] = false;
        }while(index < len);
        if(len == n){
            StringBuilder sb = new StringBuilder();
            for(int i : res) sb.append(","+i);
            System.out.println(sb.substring(1));
        }else System.out.println("None");
    }
}

发表于 2019-04-03 11:05:54 回复(0)

Java

pein531

很简单，拓扑排序模板题

import java.lang.String;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Iterator;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);     // 顶点数
        int m = Integer.parseInt(params[1]);     // 边数
        HashMap<Integer, LinkedList<Integer>> graph = new HashMap<>();
        HashMap<Integer, Integer> inDegree = new HashMap<>();
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < m; i++){
            String[] pair = br.readLine().split(" ");
            int from = Integer.parseInt(pair[1]);
            int to = Integer.parseInt(pair[0]);
            if(graph.containsKey(from)){
                graph.get(from).add(to);
            }else{
                LinkedList<Integer> neighbors = new LinkedList<>();
                neighbors.add(to);
                graph.put(from, neighbors);
            }
            inDegree.put(to, inDegree.getOrDefault(to, 0) + 1);
        }
        // 入度为0的作为起点
        for(int node = 0; node < n; node++){
            if(!inDegree.containsKey(node)){
                queue.offer(node);
            }
        }
        StringBuilder res = new StringBuilder();
        // 拓扑排序
        int count = 0;
        while(!queue.isEmpty()){
            int cur = queue.poll();
            res.append(cur).append(",");
            count ++;
            if(graph.containsKey(cur)){
                Iterator<Integer> iterator = graph.get(cur).iterator();
                while(iterator.hasNext()){
                    int next = iterator.next();
                    if(inDegree.get(next) == 1){
                        inDegree.remove(next);
                        queue.offer(next);
                    }else{
                        inDegree.put(next, inDegree.get(next) - 1);
                    }
                }
            }
        }
        if(count == n){
            // 可以品尝完所有菜肴
            res.deleteCharAt(res.length() - 1);
            System.out.println(res);
        }else{
            System.out.println("None");
        }
    }
}

发表于 2022-01-13 15:10:10 回复(0)

永冬zdx

用一个字典来存储前置条件，将条件与result比较，如果满足条件就加入到result中，同时删除字典相应内容，最后输出result

import sys
line=sys.stdin.readline().strip()
values=list(map(int,line.split()))
n=values[0]
m=values[1]
result=[]
nlist=[ i for i in range(n)]
mlist=[i for i in range(m)]
dic={}
for i in range(m):
    line = sys.stdin.readline().strip()
    values = list(map(int, line.split()))
    if values[0] in dic:
        dic[values[0]].append(values[1])
    else:
        listtmp=[values[1]]
        dic[values[0]]=listtmp

ktmp=dic.keys()
k=[]
for i in ktmp:
    k.append(i)
for i in nlist:
    if i not in k:
        result.append(i)

while len(result)<n:
    lentmp=len(result)
    for item in k:
        if set(dic[item]).issubset(set(result)):
            result.append(item)
            del dic[item]
            k.remove(item)
    if lentmp==len(result):
        result=[None]
        break

for i in range(len(result)):
    if i==len(result)-1:
        print(result[i])
    else:
        print(result[i], end=",")

发表于 2021-09-26 19:18:15 回复(0)

英语小天才

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] str = sc.nextLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        int[][] graph = new int[n][n];
        for(int i = 0;i<m;i++){
            String[] s = sc.nextLine().split(" ");
            graph[Integer.parseInt(s[0])][Integer.parseInt(s[1])]=1;
        }
        int[] res = new int[n];
        int[] visit = new int[n];
        int index = 0;
        int len = 0;
        do{
            index = len;
            for(int i = 0;i<n; i++){
                if(visit[i] == 1)contine;
                int j=0;
                while(j<n){
                    if(graph[i][j] == 1)
                        break;
                    j++;
                }
                if(j==n){
                    res[len++] = i;
                    visit[i] = 1;
                }
            }
            for(int i = index; i<len;i++){
                for(int rows = 0;rows<n;rows++){
                    graph[rows][resi] = 0;
                }
            }
        }
        while(index<len);
        if(len == n){
            StringBuilder sb = new StringBuilder();
            for(int i:res)
                sb.append(","+i);
            System.out.printIn(sb.substring(1));
        }else{
            System.out.printIn("None");
        }
    }
}

发表于 2020-03-20 19:55:19 回复(0)

T🌟

#dfs解

from collections import deque

n,m = map(int,input().split(" "))
pr = {}
nx = {}

for i in range(n):
pr[i]=[]
nx[i]=[j for j in range(n)]
nx[i].remove(i)
for _ in range(m):
cur,pre = map(int,input().split(" "))
pr[cur].append(pre)
nx[cur].remove(pre)
q = deque()
flag = 0
for d in pr:
if len(pr[d])==0:
q.append((d,[d]))

while len(q)!=0:
pre,his = q.pop()
if len(his)==n:
res = []
print(','.join([str(num) for num in his]))
flag = 1
break
else:
for cur in nx[pre]:
if cur not in his:
flag2 = 0
for i in pr[cur]:
if i not in his:
flag2 =1
if flag2 == 0:
q.appendleft((cur,his+[cur]))

if flag == 0:
print(None)

发表于 2019-04-21 07:07:59 回复(0)

tides

import collections, sys
n, m = [int(num) for num in sys.stdin.readline().split()]
indegrees = [0] * n
dic = collections.defaultdict(list)
for i in range(m):
    d, pred = [int(num) for num in sys.stdin.readline().split()]
    if d != pred:
        dic[pred].append(d)
        indegrees[d] += 1
queue = []
for i in range(n):
    if indegrees[i] == 0:
        queue.append(i)
res = []
while len(queue):
    d = queue.pop(0)
    res.append(d)
    for postd in dic[d]:
        indegrees[postd] -= 1
        if indegrees[postd] == 0:
            queue.append(postd)
if len(res) == n:
    print(','.join([str(num) for num in res]))
else:
    print(None)

发表于 2019-04-03 11:00:55 回复(0)

无法翻身的咸鱼

这道题是个拓扑排序，大致思路是建表，然后将入读为0的点放到队列中，然后通过这些入读为0的点去解锁不为0的点，解锁后如果入读为0则将其放在队列中，直到队列为空，这道题有bug，当不存在所谓的关系的时候，也就是n 0这种格式的数据没有

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long LL;

int check[50000];
int a[50000],b[50000];
vector<int> tu[50000];
int n,m,number;

int main(int argc, char const *argv[])
{
    int x,y;
    cin >> n >> m;
    if(m == 0)
    {
        for(int i = 0;i < n;i++)
        {
            if(i == n-1)
                cout << i << endl;
            else
            {
                cout << i << ",";
            }
            
        }
    }
    for(int i = 1;i <= m;i++)
    {
        cin >> x >> y;
        tu[y].push_back(x);
        a[x]++;
    }
    queue<int> qua;
    for(int i = 0;i < n;i++)
    {
        if(a[i] == 0)
            qua.push(i);
    }
    while(!qua.empty())
    {
        int u = qua.front();
        qua.pop();
        b[++number] = u;
        for(int i = 0;i < tu[u].size();i++)
        {
            int k = tu[u][i];
            a[k]--;//通过u这个入度为0的点解锁下面的点
            if(a[k] == 0)//如果这个点通过解锁入度为0则放到队列中
            {
                qua.push(k);
            }
        }
    }
    if(number != n)
    {
        cout << "None" << endl;
        return 0;
    }
    for(int i = 1;i <= number;i++)
    {
        if(i == n)
            cout << b[i] << endl;
        else
        {
            cout << b[i] << ",";
        }
    }
    return 0;
}

发表于 2019-02-26 15:53:47 回复(1)

ChessC

/*leetcode Course Schedule II原题基本上
    类似图进行dfs遍历，我们要做的就是找是否存在环，如果有环，直接false，否则我们返回其中一个遍历序列
    分成以下几步:
    1.GraphNode以及初始图关系的构建
    2.遍历初始节点，进行dfs，那么如何判断有环呢？如果我们在当前节点处dfs后，相邻的节点中有已访问的或者又
    递归到了已访问的节点之中，那么此时就是有环的
    3.根据第二步，因此我们可以用一个visit数组来标记状态,以及一个onpath数组来判定是否已经在路径上了
*/
#include <iostream>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<set<int>> graph=make_graph(numCourses,prerequisites);//构造图
        vector<int> res;
        vector<bool> onpath(numCourses,false),visited(numCourses,false);
        //分别为是否在路径上以及节点的访问状态
        for(int i=0;i<numCourses;++i)
            if(!visited[i] && dfs(graph,i,onpath,visited,res))//如果当前节点还未访问，但是dfs结果是返回true，相矛盾了
                return {};
        return res; 
    }
private:
    vector<set<int>> make_graph(int numCourses,vector<pair<int,int>>& prerequisites){
        vector<set<int>> graph(numCourses);
        for(auto pre:prerequisites)
            graph[pre.second].insert(pre.first);
        return graph;
    }
    
    bool dfs(vector<set<int>>& graph,int node,vector<bool>& onpath,vector<bool>& visited,vector<int>& res){
        if(visited[node])
            return false; //已经访问过了
        onpath[node]=visited[node]=true; //当前节点状态修改为已访问及在路径上
        for(int neigh:graph[node])
            if(onpath[neigh] || dfs(graph,neigh,onpath,visited,res)) 
                return true;
        res.push_back(node);
        return onpath[node]=false; //重新将onpath[node]置为false
    }
};

int main(){
    int n,m;
    cin>>n;
    cin>>m;
    vector<pair<int,int>> vec; //输入关系
    int num=n;
    while(n--){
        int first,second;
        cin>>first;
        cin>>second;
        vec.push_back({second,first});
    }
    Solution sol;
    vector<int> res;
    res=sol.findOrder(num,vec);
    if(res.empty())
        cout<<"None";
    else{
        for(int i=0;i<res.size()-1;++i)
            cout<<res[i]<<",";
        cout<<res[res.size()-1];
    }
    return 0;
}

反正大致是这样的思路

编辑于 2019-02-17 14:24:25 回复(0)