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...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...
【C++】纯虚函数类外可以写实现吗?
1. 答案 先说答案,可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...
沙箱虚拟化技术虚拟机容器之间的关系详解
问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西,但是如果把三者放在一起,它们之间到底什么关系?又有什么联系呢?我不是很明白!!! 就比如说: 沙箱&#…...
全面解析数据库:从基础概念到前沿应用
在数字化时代,数据已成为企业和社会发展的核心资产,而数据库作为存储、管理和处理数据的关键工具,在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理,到社交网络的用户数据存储,再到金融行业的交易记录处理&a…...
