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笔试面试备考平台_牛客网 题目大意:有n个数分别为1~n,有m个数值对(u,v)表示u要排在v左边,问至少要多少个排列才能满足所有数值对至少一次 2<n<1e6;1<m<1e6 思路:如果数值对中要求u在v左边,…...
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 协议是超文本传输协议,是客户端浏览器或其他程序“请求”与 Web 服务器响应之间的应用层通信协议。HTTPS主要是由HTTPSSL构建的可进行加密传输、身份认证的一种安全通信通道。32、http 和 https 的区别 ? 1、https协议需要到ca申请证书&…...
Docker 安全及日志管理与https部署
容器的安全性问题的根源在于容器和宿主机共享内核。如果容器里的应用导致Linux内核崩溃,那么整个系统可能都会崩溃。与虚拟机是不同的,虚拟机并没有与主机共享内核,虚拟机崩溃一般不会导致宿主机崩溃。 Docker 容器与虚拟机的区别 虚拟机通…...
2.3 HLSL常用函数
一、函数介绍 函数图像参考网站:Graphtoy 1.基本数学运算 函数 含义 示例图 min(a,b) 返回a、b中较小的数值 mul(a,b) 两数相乘用于矩阵计算 max(a,b) 返回a、b中较大的数值 abs(a) 返回a的绝对值 round(x) 返回与x最近的整数 sqrt(x) 返回x的…...
互联网的发展
概述 互联网是现代社会中举足轻重的一个领域,它的发展对于人类的生活和工作方式产生了深远的影响。互联网的发展经历了几个阶段,从初创阶段到如今的高度普及和深入应用,本文将详细介绍互联网的发展状况。 第一阶段:互联网的起源…...
STM32 CAN通讯实验程序
目录 STM32 CAN通讯实验 CAN硬件原理图 CAN外设原理图 TJA1050T硬件描述 实验线路图 回环实验 CAN头文件配置 CAN_GPIO_Config初始化 CAN初始化结构体 CAN筛选器结构体 接收中断优先级配置 接收中断函数 main文件 实验现象 补充 STM32 CAN通讯实验 CAN硬件原理图…...
Python代码片段之Django静态文件URL的配置
首先要说明这段python代码并不完整,而且我也没有做过测试,只是我在工作时参考了其中的一些个方法。这是我在找python相关源码资料里看到的一段代码,是Django静态文件URL配置代码片段2,代码中有些方法还是挺技巧的,做其…...
基于飞桨paddle的极简方案构建手写数字识别模型测试代码
基于飞桨paddle的极简方案构建手写数字识别模型测试代码 原始测试图片为255X252的图片 因为是极简方案采用的是线性回归模型,所以预测结果数字不一致 本次预测的数字是 [[3]] 测试结果: PS E:\project\python> & D:/Python39/python.exe e:/pro…...
soft ip与hard ip
ip分soft和hard两种,soft就是纯代码,买过来要自己综合自己pr。hard ip如mem和analog与工艺有关。 mem的lib和lef是memory compiler产生的,基于bitcell,是foundry给的。 我正在「拾陆楼」和朋友们讨论有趣的话题,你⼀起…...
MyBatisPlus从入门到精通-2
接着上一讲的Mp的分页功能 下面我们讲解条件查询功能和其他功能 解决一下日志输出和banner问题 每次卞就会输出这些日志 很不美观,现在我们关闭一下 这样建个xml,文件名为logback.xml 文件内容改成这样 配置了logback但是里面什么都没写就不会说有日…...
AI面试官:Asp.Net 中使用Log4Net (一)
AI面试官:Asp.Net 中使用Log4Net (一) 当面试涉及到使用log4net日志记录框架的相关问题时,通常会聚焦在如何在.NET或.NET Core应用程序中集成和使用log4net。以下是一些关于log4net的面试题目,以及相应的解答、案例和代码: 文章目…...
Selenium自动化元素定位方式与浏览器测试脚本
Selenium八大元素定位方法 Selenium可以驱动浏览器完成各种操作,比如模拟点击等。要想操作一个元素,首先应该识别这个元素。人有各种的特征(属性),我们可以通过其特征找到人,如通过身份证号、姓名、家庭住…...
人机交互与人机混合智能的区别
人机交互和人机融合智能是两个相关但不完全相同的概念: 人机交互是指人与计算机之间的信息交流和互动过程。它关注的是如何设计和实现用户友好的界面,以便人们能够方便、高效地与计算机进行沟通和操作。人机交互通常强调用户体验和界面设计,旨…...
【项目】轻量级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 在线打开的方法有哪些?这个问题和我之前回答过的「Sketch 可以在线编辑吗?」是一样的答案,没有。很遗憾,Sketch 没有在线打开的方法,Sketch 也做不到可以在线编辑。那么,那些广告里出现的设计软件工…...
CSS Flex 笔记
1. Flexbox 术语 Flex 容器可以是<div> 等,对其设置属性:display: flex, justify-content 是沿主轴方向调整元素,align-items 是沿交叉轴对齐元素。 2. Cheatsheet 2.1 设置 Flex 容器,加粗的属性为默认值 2.1.1 align-it…...
Markdown常用标签及其用途-有示例
Markdown常用标签及其用途 Markdown是一种轻量级标记语言,具有简洁易读的特点。下面是一些常用的Markdown标签以及它们的用途,并附带一些示例: 标题 用于创建不同级别的标题,可通过添加一到六个#符号来表示不同级别的标题。 #…...
25.1 Knife4j-Swagger的增强插件
1.Knife4j概述 Knife4j是一款基于Swagger UI的增强插件,它可以为Spring Boot项目生成美观且易于使用的API文档界面。它是Swagger UI的增强版,提供了更多的功能和定制选项,使API文档更加易读和易于理解。 2.Knife4j使用 Knife4j 集Swagger2…...
用flask run代替flask run --debug
安装python-dotenv依赖。 在项目根目录下新建.flaskenv文件,并作如下配置: FLASK_ENVdevelopment FLASK_DEBUG1...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
Bean 作用域有哪些?如何答出技术深度?
导语: Spring 面试绕不开 Bean 的作用域问题,这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开,结合典型面试题及实战场景,帮你厘清重点,打破模板式回答,…...
xmind转换为markdown
文章目录 解锁思维导图新姿势:将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件(ZIP处理)2.解析JSON数据结构3:递归转换树形结构4:Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...
Mac flutter环境搭建
一、下载flutter sdk 制作 Android 应用 | Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 1、查看mac电脑处理器选择sdk 2、解压 unzip ~/Downloads/flutter_macos_arm64_3.32.2-stable.zip \ -d ~/development/ 3、添加环境变量 命令行打开配置环境变量文件 ope…...
【51单片机】4. 模块化编程与LCD1602Debug
1. 什么是模块化编程 传统编程会将所有函数放在main.c中,如果使用的模块多,一个文件内会有很多代码,不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里,在.h文件里提供外部可调用函数声明,其他.c文…...
Android Framework预装traceroute执行文件到system/bin下
文章目录 Android SDK中寻找traceroute代码内置traceroute到SDK中traceroute参数说明-I 参数(使用 ICMP Echo 请求)-T 参数(使用 TCP SYN 包) 相关文章 Android SDK中寻找traceroute代码 设备使用的是Android 11,在/s…...
