PAT日志 1146「建议收藏」

PAT日志 1146「建议收藏」顽强的小白1146TopologicalOrder(25分)ThisisaproblemgivenintheGraduateEntranceExamin2018:WhichofthefollowingisNOTatopologicalorderobtainedfromthegivendirectedgraph?Nowyouare…

大家好,又见面了,我是你们的朋友全栈君。

顽强的小白

1146 Topological Order (25 分)

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.
在这里插入图片描述

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
5
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:

3 4

题目解析

判断所给的序列是不是拓扑排序
我的思路很暴力,拓扑排序本来就是一个一个拿掉图上的顶点,这些被拿掉的顶点只有一个要求,就是不能有其他顶点指向它,因此我的思路就是,判断当点要拿掉的结点有没有被谁指着,如果有就不是拓扑排序。

代码实现

#include <cstdio> 
#include <vector> 
#include <algorithm> 

using namespace std; 

const int maxn=1005;

bool vis[maxn];
int G[maxn][maxn];
vector<int> ans;int main(){ 
   
 fill(G[0],G[0]+maxn*maxn,0);
 int n,e,u,v;
 scanf("%d%d",&n,&e);
 for(int i=0;i<e;++i){ 
   
  scanf("%d%d",&u,&v);
  G[u][v]=1;
 }
 int m;
 scanf("%d",&m);
 for(int i=0;i<m;++i){ 
   
  fill(vis,vis+n+1,true); //初始状态 灯全亮 
  int flag=0;
  for(int j=0;j<n;++j){ 
   
   scanf("%d",&u);
   for(int k=1;k<=n;++k){ 
   
    if(vis[k]==true&&G[k][u]==1){ 
   
     flag=1;
     break; 
    }
   }
   vis[u]=false;   //把这个顶点灭灯 
  }
  if(flag==1) ans.push_back(i);
 }
 for(int i=0;i<ans.size();++i) { 
   
  printf("%d",ans[i]);
  if(i<ans.size()-1) printf(" ");
  else printf("\n");
 }
} 
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/133288.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • md5值是不是哈希值_2000哈希

    md5值是不是哈希值_2000哈希MD5isachecksumorhashcalculationmethodforfiles.MD5checksumconsistsof128-bitvaluewhichisgenerallyexpressedasthehexadecimalformatwithwhichconsistof32characters.MD5是文件的校验和或哈希…

  • 选一个适合自己的加密芯片,加密IC,如何才能真正的做到不被激活成功教程。[通俗易懂]

    选一个适合自己的加密芯片,加密IC,如何才能真正的做到不被激活成功教程。[通俗易懂]做嵌入式产品,最头痛的事情就是害怕自己的代码给别人读出来,不需要通过自己,人家直接拿去生产了。所以要保护自己的最好方式就是使用硬加密IC的方式。当然有句话说的好“这世上没有激活成功教程不了的加密算法”。每一个加密芯片都有它的不足和优势,今天我不说如果激活成功教程加密IC,我拿几个产品来对比,只讲它的优点和缺点。     ATSHA204:使用SHA-256算法进行加密操作,内置16*32字节的slot(E

  • 程序员的生存法则_程序员的一生

    程序员的生存法则_程序员的一生前几天,和国内某知名企业的行销一线喝茶聊天,他一直在抱怨自己的上司很差劲,一直允诺追加奖金,但是月底考评结果却给的很差,奖金也没别人的多,所以他想调别的部门。我很是惊诧,这公司是你们家开的?怎么可以想调就调?他笑了笑说,你不懂职场生存法则吗?    他的工作需要经常出差,全国各地跑。上次是去江西,他知道部门A的老大老家在江西,就主动去找A部门老大,告之有个出差机会,要不要一起?后来我才明白“要不

  • JAVA 正则表达式_正则表达式文档

    JAVA 正则表达式_正则表达式文档一、校验数字的表达式1数字:^[0-9]*$2n位的数字:^\d{n}$3至少n位的数字:^\d{n,}$4m-n位的数字:^\d{m,n}$5零和非零开头的数字:^(0|[1-9][0-9]*)$6非零开头的最多带两位小数的数字:^([1-9][0-9]*)+(.[0-9]{1,2})?$7带1-2位小数的正数或负数:^(\-)?\d+(\.\d{1,2})?…

  • Java学习路线图[通俗易懂]

    Java学习路线图[通俗易懂]一、Java学习路线图   二、Java学习路线图——视频篇 六大阶段学完后目标知识点配套免费资源(视频+笔记+源码+模板)密码     第一阶段Java基础 入门学习周期:35天学完后目标:1.可进行小型应用程序开

  • csgo绑定一键跳投创意工坊(csgo取消一键跳投)

    此篇文章我写出三种方法本人最推荐第三种!!!方法一废话从不多说直接在电脑上新建一个记事本命名随意(我的命名为1)在记事本里面直接粘贴以下代码alias+jumpthrow”+jump;-attack”alias-jumpthrow”-jump”bindN+jumpthrow(N为所绑定的按键为了醒目我加的粗可以随意更改)如图所示录入后记得保存然后在游戏中打开控制台一般是~键然…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号