1146 Topological Order(31行代码+详细注释)

这篇具有很好参考价值的文章主要介绍了1146 Topological Order(31行代码+详细注释)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

分数 25

全屏浏览题目

作者 CHEN, Yue

单位 浙江大学

This is a problem given in the Graduate Entrance Exam in 2018: Which of the following is NOT a topological order obtained from the given directed graph? Now you are supposed to write a program to test each of the options.

1146 Topological Order(31行代码+详细注释)

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (≤ 1,000), the number of vertices in the graph, and M (≤ 10,000), the number of directed edges. Then M lines follow, each gives the start and the end vertices of an edge. The vertices are numbered from 1 to N. After the graph, there is another positive integer K (≤ 100). Then K lines of query follow, each gives a permutation of all the vertices. All the numbers in a line are separated by a space.

Output Specification:

Print in a line all the indices of queries which correspond to "NOT a topological order". The indices start from zero. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line. It is graranteed that there is at least one answer.

Sample Input:

6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
6
5 2 3 6 4 1
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6

Sample Output:

0 4 5

鸣谢用户柳汀洲补充数据!

代码长度限制

16 KB

时间限制

200 ms

内存限制

64 MB

 算法思想:拓扑序列各相邻结点的顺序满足开始输入的边的端点顺序

举例如下:

判断序列5 2 3 6 4 1,序列下标分别为1 2 3 4 5 6,序列中1和2的下标分别为6和1不满足边的端点顺序故不是拓扑序列

#include<bits/stdc++.h>
using namespace std;
const int N=1009,M=10010;
int n,m;  
struct edge{
    int v1,v2;
}e[M];
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++)cin>>e[i].v1>>e[i].v2;//输入边 
    int k;
    cin>>k;
    int first=1;//用于第一次不是拓扑序列的输出 
    for(int i=0;i<k;i++){
        bool flag=true;
        vector<int>v;
        int pos[N];//记录询问序列各节点的位置 
        for(int j=0;j<n;j++){//询问序列各节点插入并记录位置 
            int t;
            cin>>t;
            v.push_back(t);
            pos[t]=j;
        }
        for(int j=0;j<n;j++){//该序列的结点先后位置若与边的端点先后顺序矛盾则不是拓扑序列 
            if(pos[e[j].v1]>pos[e[j].v2])flag=false;
        }
        if(!flag&&first)first=0,cout<<i;//第一次不是拓扑序列输出i 
        else if(!flag)cout<<' '<<i;//之后每次多输出个空格 
    }
    return 0;
}
文章来源地址https://www.toymoban.com/news/detail-459718.html

到了这里,关于1146 Topological Order(31行代码+详细注释)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • ResNeXt代码复现+超详细注释(PyTorch)

    ResNeXt就是一种典型的混合模型,由基础的Inception+ResNet组合而成,本质在gruops分组卷积,核心创新点就是用一种平行堆叠相同拓扑结构的blocks代替原来 ResNet 的三层卷积的block,在不明显增加参数量级的情况下提升了模型的准确率,同时由于拓扑结构相同,超参数也减少了,便

    2024年02月15日
    浏览(50)
  • ResNet代码复现+超详细注释(PyTorch)

    关于ResNet的原理和具体细节,可参见上篇解读:经典神经网络论文超详细解读(五)——ResNet(残差网络)学习笔记(翻译+精读+代码复现) 接下来我们就来复现一下代码。 源代码比较复杂,感兴趣的同学可以上官网学习:  https://github.com/pytorch/vision/tree/master/torchvision 本

    2024年02月11日
    浏览(43)
  • 【算法】顺时针打印矩阵(图文详解,代码详细注释

    目录 题目 代码如下: 输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。例如:如果输入如下矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则打印出数字:1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 这一道题乍一看,没有包含任何复杂的数据结构和高级算法,似乎蛮简单的。但

    2024年04月26日
    浏览(37)
  • 非极大值抑制详细原理(NMS含代码及详细注释)

    作者主页: 爱笑的男孩。的博客_CSDN博客-深度学习,YOLO,活动领域博主 爱笑的男孩。擅长深度学习,YOLO,活动,等方面的知识,爱笑的男孩。关注算法,python,计算机视觉,图像处理,深度学习,pytorch,神经网络,opencv领域. https://blog.csdn.net/Code_and516?type=collect 个人介绍:打工人。 分享内容

    2023年04月21日
    浏览(55)
  • 五子棋小游戏 java版(代码+详细注释)

    游戏展示         这周闲来无事,再来写个五子棋小游戏。基本功能都实现了,包括人人对战、人机对战。界面布局和功能都写的还行,没做到很优秀,但也不算差。如有需要,做个java初学者的课程设计或者自己写着玩玩也都是不错的(非常简单,小白照着就能写出来)。

    2024年02月07日
    浏览(47)
  • 1118 Birds in Forest(35行代码+详细注释)

    分数 25 全屏浏览题目 切换布局 作者 CHEN, Yue 单位 浙江大学 Some scientists took pictures of thousands of birds in a forest. Assume that all the birds appear in the same picture belong to the same tree. You are supposed to help the scientists to count the maximum number of trees in the forest, and for any pair of birds, tell if they are

    2024年02月08日
    浏览(59)
  • 1063 Set Similarity(详细注释+35代码+set的妙用)

    分数 25 全屏浏览题目 作者 CHEN, Yue 单位 浙江大学 Given two sets of integers, the similarity of the sets is defined to be Nc​/Nt​×100%, where Nc​ is the number of distinct common numbers shared by the two sets, and Nt​ is the total number of distinct numbers in the two sets. Your job is to calculate the similarity of any give

    2024年02月05日
    浏览(35)
  • 通俗易懂的知识蒸馏 Knowledge Distillation(下)——代码实践(附详细注释)

    第一步:导入所需要的包 第二步:定义教师模型 教师模型网络结构(此处仅举一个例子):卷积层-卷积层-dropout-dropout-全连接层-全连接层 第三步:定义训练教师模型方法 正常的定义一个神经网络模型 第四步:定义教师模型测试方法 正常的定义一个神经网络模型 第五步:

    2024年02月12日
    浏览(42)
  • BP神经网络预测回归MATLAB代码(代码完整可直接用,注释详细,可供学习)

    BP神经网络预测回归MATLAB代码(代码完整可用,复制后即可运行使用,操作简单) (1)BP神经网络的知识想必不用再过多介绍,本篇文章从实际应用的角度,针对新手应用者,针对不需要过多了解BP,但是需使用MATLAB进行BP预测使用的童鞋们(就是那些我不需要懂,能用就行的

    2023年04月09日
    浏览(47)
  • 最长公共子序列(详细代码 注释 分析 以及求出最长公共子序列内容方法)

    文章有些长,希望能够耐心看完,并且对你有帮助,文章是自己看了书之后,总结的,如果有什么错误的地方,欢迎指出。 一些基本的概念: 子序列: 原序列中删除若干个元素得到的序列,即原序列中可以不连续的一段 子串: 原序列中任意个连续的序列元素组成的序列,

    2023年04月15日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包