当前位置: 首页 > news >正文

Fine Logic

登录—专业IT笔试面试备考平台_牛客网

题目大意:有n个数分别为1~n,有m个数值对(u,v)表示u要排在v左边,问至少要多少个排列才能满足所有数值对至少一次

2<=n<=1e6;1<=m<=1e6

思路:如果数值对中要求u在v左边,v在w左边,那么u就得在w左边,所以他们之间具有传递性,同时,如果w要求在u左边,那么1个排列是肯定满足不了的,那么我们从每个数值对的u向v建边,有向图中无环和能用1个排列表示是充分必要条件,而如果有环时,最复杂的情况就是完全图,这是可以用1,2...n和n,n-1...1两个排列表示,可以看出这两个排列已经包含了题目中所有可能的图,我们再来看无环的情况,如果u1和u2都指向v,那么我们要把u1,u2都放在v的左边,所以取拓扑序即可

#include<bits/stdc++.h>
//#include<__msvc_all_public_headers.hpp>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
ll MOD = 1e9 + 7;
vector<int>g[N];
int ind[N];
vector<int>ans;
int n, m;
void init(int x)
{ans.clear();for (int i = 1; i <= x; i++){g[i].clear();ind[i] = 0;}
}
bool bfs()
{//拓扑排序queue<int>q;for (int i = 1; i <= n; i++){if (!ind[i]){q.push(i);ans.push_back(i);}}while (!q.empty()){int u = q.front();q.pop();for (int i = 0; i < g[u].size(); i++){int v = g[u][i];if (!--ind[v]){//将子节点入度为0的放入答案q.push(v);ans.push_back(v);}}}if (ans.size() < n)return 0;//有点入度仍不为0,说明有环return 1;
}
int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);int t;
t=1;while (t--){	cin >> n >> m;init(n);for (int i = 1; i <= m; i++){int u, v;cin >> u >> v;g[u].push_back(v);ind[v]++;//记录入度}bool temp=bfs();if (!temp){//有环直接输出正序和反序排列cout << 2 << endl;for (int i = 1; i <= n; i++){cout << i << " ";}cout << endl;for (int i = n; i >= 1; i--){cout << i << " ";}cout << endl;continue;}cout << 1 << endl;for (int i = 0; i < ans.size(); i++){cout << ans[i] << " ";}cout << endl;}return 0;
}

相关文章:

Fine Logic

登录—专业IT笔试面试备考平台_牛客网 题目大意&#xff1a;有n个数分别为1~n&#xff0c;有m个数值对(u,v)表示u要排在v左边&#xff0c;问至少要多少个排列才能满足所有数值对至少一次 2<n<1e6;1<m<1e6 思路&#xff1a;如果数值对中要求u在v左边&#xff0c;…...

Neo4j图数据基本操作

Neo4j 文章目录 Neo4jCQL结点和关系增删改查匹配语句 根据标签匹配节点根据标签和属性匹配节点删除导入数据目前的问题菜谱解决的问题 命令行窗口 neo4j.bat console 导入rdf格式的文件 :GET /rdf/ping CALL n10s.graphconfig.init(); //初始化 call n10s.rdf.import.fetch(&q…...

前端JavaScript面试100问(中)

31、http 的理解 ? HTTP 协议是超文本传输协议&#xff0c;是客户端浏览器或其他程序“请求”与 Web 服务器响应之间的应用层通信协议。HTTPS主要是由HTTPSSL构建的可进行加密传输、身份认证的一种安全通信通道。32、http 和 https 的区别 ? 1、https协议需要到ca申请证书&…...

Docker 安全及日志管理与https部署

容器的安全性问题的根源在于容器和宿主机共享内核。如果容器里的应用导致Linux内核崩溃&#xff0c;那么整个系统可能都会崩溃。与虚拟机是不同的&#xff0c;虚拟机并没有与主机共享内核&#xff0c;虚拟机崩溃一般不会导致宿主机崩溃。 Docker 容器与虚拟机的区别 虚拟机通…...

2.3 HLSL常用函数

一、函数介绍 函数图像参考网站&#xff1a;Graphtoy 1.基本数学运算 函数 含义 示例图 min(a,b) 返回a、b中较小的数值 mul(a,b) 两数相乘用于矩阵计算 max(a,b) 返回a、b中较大的数值 abs(a) 返回a的绝对值 round(x) 返回与x最近的整数 sqrt(x) 返回x的…...

互联网的发展

概述 互联网是现代社会中举足轻重的一个领域&#xff0c;它的发展对于人类的生活和工作方式产生了深远的影响。互联网的发展经历了几个阶段&#xff0c;从初创阶段到如今的高度普及和深入应用&#xff0c;本文将详细介绍互联网的发展状况。 第一阶段&#xff1a;互联网的起源…...

STM32 CAN通讯实验程序

目录 STM32 CAN通讯实验 CAN硬件原理图 CAN外设原理图 TJA1050T硬件描述 实验线路图 回环实验 CAN头文件配置 CAN_GPIO_Config初始化 CAN初始化结构体 CAN筛选器结构体 接收中断优先级配置 接收中断函数 main文件 实验现象 补充 STM32 CAN通讯实验 CAN硬件原理图…...

Python代码片段之Django静态文件URL的配置

首先要说明这段python代码并不完整&#xff0c;而且我也没有做过测试&#xff0c;只是我在工作时参考了其中的一些个方法。这是我在找python相关源码资料里看到的一段代码&#xff0c;是Django静态文件URL配置代码片段2&#xff0c;代码中有些方法还是挺技巧的&#xff0c;做其…...

基于飞桨paddle的极简方案构建手写数字识别模型测试代码

基于飞桨paddle的极简方案构建手写数字识别模型测试代码 原始测试图片为255X252的图片 因为是极简方案采用的是线性回归模型&#xff0c;所以预测结果数字不一致 本次预测的数字是 [[3]] 测试结果&#xff1a; PS E:\project\python> & D:/Python39/python.exe e:/pro…...

soft ip与hard ip

ip分soft和hard两种&#xff0c;soft就是纯代码&#xff0c;买过来要自己综合自己pr。hard ip如mem和analog与工艺有关。 mem的lib和lef是memory compiler产生的&#xff0c;基于bitcell&#xff0c;是foundry给的。 我正在「拾陆楼」和朋友们讨论有趣的话题&#xff0c;你⼀起…...

MyBatisPlus从入门到精通-2

接着上一讲的Mp的分页功能 下面我们讲解条件查询功能和其他功能 解决一下日志输出和banner问题 每次卞就会输出这些日志 很不美观&#xff0c;现在我们关闭一下 这样建个xml&#xff0c;文件名为logback.xml 文件内容改成这样 配置了logback但是里面什么都没写就不会说有日…...

AI面试官:Asp.Net 中使用Log4Net (一)

AI面试官&#xff1a;Asp.Net 中使用Log4Net (一) 当面试涉及到使用log4net日志记录框架的相关问题时&#xff0c;通常会聚焦在如何在.NET或.NET Core应用程序中集成和使用log4net。以下是一些关于log4net的面试题目&#xff0c;以及相应的解答、案例和代码&#xff1a; 文章目…...

Selenium自动化元素定位方式与浏览器测试脚本

Selenium八大元素定位方法 Selenium可以驱动浏览器完成各种操作&#xff0c;比如模拟点击等。要想操作一个元素&#xff0c;首先应该识别这个元素。人有各种的特征&#xff08;属性&#xff09;&#xff0c;我们可以通过其特征找到人&#xff0c;如通过身份证号、姓名、家庭住…...

人机交互与人机混合智能的区别

人机交互和人机融合智能是两个相关但不完全相同的概念&#xff1a; 人机交互是指人与计算机之间的信息交流和互动过程。它关注的是如何设计和实现用户友好的界面&#xff0c;以便人们能够方便、高效地与计算机进行沟通和操作。人机交互通常强调用户体验和界面设计&#xff0c;旨…...

【项目】轻量级HTTP服务器

文章目录 一、项目介绍二、前置知识2.1 URI、URL、URN2.2 CGI2.2.1 CGI的概念2.2.2 CGI模式的实现2.2.3 CGI的意义 三、项目设计3.1 日志的编写3.2 套接字编写3.3 HTTP服务器实现3.4 HTTP请求与响应结构3.5 EndPoint类的实现3.5.1 EndPoint的基本逻辑3.5.2 读取请求3.5.3 构建响…...

sketch如何在线打开?有没有什么软件可以辅助

Sketch 在线打开的方法有哪些&#xff1f;这个问题和我之前回答过的「Sketch 可以在线编辑吗&#xff1f;」是一样的答案&#xff0c;没有。很遗憾&#xff0c;Sketch 没有在线打开的方法&#xff0c;Sketch 也做不到可以在线编辑。那么&#xff0c;那些广告里出现的设计软件工…...

CSS Flex 笔记

1. Flexbox 术语 Flex 容器可以是<div> 等&#xff0c;对其设置属性&#xff1a;display: flex, justify-content 是沿主轴方向调整元素&#xff0c;align-items 是沿交叉轴对齐元素。 2. Cheatsheet 2.1 设置 Flex 容器&#xff0c;加粗的属性为默认值 2.1.1 align-it…...

Markdown常用标签及其用途-有示例

Markdown常用标签及其用途 Markdown是一种轻量级标记语言&#xff0c;具有简洁易读的特点。下面是一些常用的Markdown标签以及它们的用途&#xff0c;并附带一些示例&#xff1a; 标题 用于创建不同级别的标题&#xff0c;可通过添加一到六个#符号来表示不同级别的标题。 #…...

25.1 Knife4j-Swagger的增强插件

1.Knife4j概述 Knife4j是一款基于Swagger UI的增强插件&#xff0c;它可以为Spring Boot项目生成美观且易于使用的API文档界面。它是Swagger UI的增强版&#xff0c;提供了更多的功能和定制选项&#xff0c;使API文档更加易读和易于理解。 2.Knife4j使用 Knife4j 集Swagger2…...

用flask run代替flask run --debug

安装python-dotenv依赖。 在项目根目录下新建.flaskenv文件&#xff0c;并作如下配置&#xff1a; FLASK_ENVdevelopment FLASK_DEBUG1...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...