UVa11324 - The Largest Clique
Online Judge
题目大意:有一张n个点m条边的图,现对于每一个点u,建立一条边连接它和所有它能到达的点,问满足所有点之间都有边的分量的大小最大是多少
0<=n<=1000;0<=m<=50000
思路:根据建新图的规则可知,一个点会和它能到达的所有点构成一个合法的分量,那么从入度为0的点开始组成的这样一个分量一定是最大的,但是因为图中有环,所以没法直接统计这样的分量的大小,所以要先用tarjan将所有强量通分量缩成一个点,再在新图中用记忆化搜索找上述的分量
//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int head[N], head2[N];
struct Edge
{int v, next;
}e[N * N], e2[N * N];
int dfn[N], low[N];
int c1 = 0, c2 = 0;
void addedge(int u, int v)
{//原图e[++c1].v = v;e[c1].next = head[u];head[u] = c1;
}
void addedge2(int u, int v)
{//缩点后的新图e2[++c2].v = v;e2[c2].next = head2[u];head2[u] = c2;
}
bool vis[N];
int cnt = 0;
int ans = 0;
stack<int>s;
int siz[N];
pair<int, int>edge[N * N];
int n, m;
int cnts[N];
int scc[N];
void tarjan(int u)
{//将图拆解成强连通分量的组合cnt++;//访问次序dfn[u] = low[u] = cnt;//每个点的访问次序,在第几个强连通分量里 s.push(u);//储存dfs中待处理的点vis[u] = 1;//在栈内待处理for (int i = head[u]; ~i; i=e[i].next){int v = e[i].v;if (!dfn[v]){//子节点没被访问过tarjan(v);low[u] = min(low[u], low[v]);//和子节点合并成一个强连通分量}else if (vis[v]){//重复访问了栈内的节点low[u] = min(low[u], low[v]);//这两个点一定在一个强连通分量内}}if (dfn[u] == low[u]){//当前点是这个强连通分量的第一个点,也就是这个分量都已处理完毕int temp = 0;//记录强连通分量的点数ans++;//第几个强连通分量while (!s.empty() && s.top() != u){//将这个强量通分量内的点全部弹出 vis[s.top()] = 0;//不在栈内scc[s.top()] = ans;//每个点属于哪个强连通分量temp++;s.pop();}temp++;vis[s.top()] = 0;//第一个点也要弹出scc[s.top()] = ans;s.pop();siz[ans] = temp;//这个连通块里面几个点}
}
int in[N];
void init()
{c1 = c2 = 0;for (int i = 1; i <= n; i++){vis[i] = 0;dfn[i] = low[i] = siz[i] = 0;head[i] = head2[i] = -1;cnts[i] = 0;in[i] = 0;}while (!s.empty()){s.pop();}cnt = ans = 0;
}
int dfs(int u)
{//记忆化搜索能到达多少个点if (cnts[u]){return cnts[u];}int ma = 0;for (int i = head2[u]; ~i; i=e2[i].next){int v = e2[i].v;ma = max(ma, dfs(v));//取子节点里面最大的}cnts[u] = siz[u] + ma;//这个歌两桶快的大小加子节点传来的值return cnts[u];
}
void solve()
{cin >> n >> m;init();for (int i = 1; i <= m; i++){int u, v;cin >> u >> v;edge[i] = { u,v };addedge(u, v);}for (int i = 1; i <= n; i++){if (!dfn[i])//所有没处理的点都要处理tarjan(i);}for (int i = 1; i <= m; i++){int u = edge[i].first, v = edge[i].second;if (scc[u] != scc[v]){//两个点不在一个强连通分块里addedge2(scc[u], scc[v]);//建新图in[scc[v]]++;}}int out = 0;for (int i = 1; i <= n; i++){if (!in[i]){//从入度为0的点出发开始搜out = max(out, dfs(i));}}cout << out << '\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--){solve();}return 0;
}
相关文章:
UVa11324 - The Largest Clique
Online Judge 题目大意:有一张n个点m条边的图,现对于每一个点u,建立一条边连接它和所有它能到达的点,问满足所有点之间都有边的分量的大小最大是多少 0<n<1000;0<m<50000 思路:根据建新图的规则可知&am…...
【Linux】TCP的服务端(守护进程) + 客户端
文章目录 📖 前言1. 服务端基本结构1.1 类成员变量:1.2 头文件1.3 初始化:1.3 - 1 全双工与半双工1.3 - 2 inet_aton1.3 - 3 listen 2. 服务端运行接口2.1 accept:2.2 服务接口: 3. 客户端3.1 connect:3.2 …...
1.7. 找出数组的第 K 大和原理及C++实现
题目 给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。 数组的 第 k 大和 定义为:可以获得的第 k 个 最大 子序列和(子序列和允许出现重复) 返回数组的 第 k 大和 。 子序列是一个可以由其他数…...
基于微信小程序的付费自习室
博主介绍:✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 文章目录 1 简介2 技术栈3 需求分析3.1用户需求分析3.1.1 学生用户3.1.3 管理员用户 4 数据库设计4.4.1 E…...
纪念在CSDN的2048天
时间真快~...
云原生Kubernetes:简化K8S应用部署工具Helm
目录 一、理论 1.HELM 2.部署HELM2 3.部署HELM3 二、实验 1.部署 HELM2 2.部署HELM3 三、问题 1.api版本过期 2.helm初始化报错 3.pod状态为ImagePullBackOff 4.helm 命令显示 no repositories to show 的错误 5.Helm安装报错 6.git命令报错 7.CentOS 7 下git c…...
qml保姆级教程五:视图组件
💂 个人主页:pp不会算法v 🤟 版权: 本文由【pp不会算法v】原创、在CSDN首发、需要转载请联系博主 💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦 QML系列教程 QML教程一:布局组件 文章目录 列表视图ListVi…...
2310d编译不过
struct A {this(int[] data) safe { a data; }int[] a; }void main() safe {int[3] test [1, 2, 3];A a A(test); }应该给data参数加上return scope.或让构造器为模板参数来推导,否则,构造器可以把栈分配切片赋值给全局变量....
CleanMyMac X4.14.1最新版本下载
CleanMyMac X是一个功能强大的Mac清理软件,它的设计理念是提供多个模块,包括垃圾清理、安全保护、速度优化、应用程序管理和文档管理粉碎等,以满足用户的不同需求。软件的界面简洁直观,让用户能够轻松进行日常的清理操作。 使用C…...
芯驰D9评测(3)--建立开发环境
1. 建立交叉编译链接环境 官网下载的SDK包中就有交叉工具链,米尔提供的这个 SDK 中除了包含各种源代码外还提供了必要的交叉工具链,可以直接用于编译应用程序等。 用户可以直接使用次交叉编译工具链来建立一个独立的开发环境,可单独编译…...
阿里云服务器IP地址查询方法(公网IP和私网IP)
阿里云服务器IP地址在哪查看?在云服务器ECS管理控制台即可查看,阿里云服务器IP地址包括公网IP和私有IP地址,阿里云百科分享阿里云服务器IP地址查询方法: 目录 阿里云服务器IP地址查询 阿里云服务器IP地址查询 1、登录到阿里云服…...
第47节——使用bindActionCreators封装actions模块
一、什么是action creators 1、概念 在Redux中,Action Creators是一种函数,它用于创建一个描述应用程序状态变化的action对象。Action对象是一个普通JavaScript对象,它包含一个描述action类型的字符串属性(通常称为“type”&…...
QT、c/c++通过宏自动判断平台
QT、c/c通过宏自动判断平台 Chapter1 QT、c/c通过宏自动判断平台 Chapter1 QT、c/c通过宏自动判断平台 原文链接:https://blog.csdn.net/qq_32348883/article/details/123063830 背景 为了更好的进行跨平台移植、编译、调试。 具体操作 宏操作 #ifdef _WIN32//d…...
对比表:阿里云轻量应用服务器和服务器性能差异
阿里云服务器ECS和轻量应用服务器有什么区别?轻量和ECS优缺点对比,云服务器ECS是明星级云产品,适合企业专业级的使用场景,轻量应用服务器是在ECS的基础上推出的轻量级云服务器,适合个人开发者单机应用访问量不高的网站…...
中国1km分辨率月最低温和最高温度数据集(1901-2020)
简介: 中国1km分辨率月最低温度数据集(1901-2020)是根据CRU发布的全球0.5气候数据集以及WorldClim发布的全球高分辨率气候数据集,通过Delta空间降尺度方案在中国地区降尺度生成的。使用了496个独立气象观测点数据进行验证&#x…...
EasyX图形库note4,动画及键盘交互
大家好,这里是Dark Flame Master,专栏从这篇开始就会变得很有意思,我们可以利用今天所学的只是实现很多功能,同样为之后的更加好玩的内容打下基础,从这届开始将会利用所学的知识制作一些小游戏,废话不多说&…...
C++设计模式-原型(Prototype)
目录 C设计模式-原型(Prototype) 一、意图 二、适用性 三、结构 四、参与者 五、代码 C设计模式-原型(Prototype) 一、意图 用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象。 二、适用性 当…...
[补题记录] Atcoder Beginner Contest 322(E)
URL:https://atcoder.jp/contests/abc322 目录 E Probelm/题意 Thought/思路 Code/代码 E Probelm/题意 有 N 个改进计划,每个计划可以执行一次;有 K 个参数,每个计划可以将所有参数提升固定值,即计划 i 可以为第…...
目标检测算法改进系列之Backbone替换为FocalNet
FocalNet 近些年,Transformers在自然语言处理、图像分类、目标检测和图像分割上均取得了较大的成功,归根结底是自注意力(SA :self-attention)起到了关键性的作用,因此能够支持输入信息的全局交互。但是由于…...
buuctf-[BSidesCF 2020]Had a bad day 文件包含
打开环境 就两个按钮,随便按按 url变了 还有 像文件包含,使用php伪协议读取一下,但是发现报错,而且有两个.php,可能是自己会加上php后缀 所以把后缀去掉 /index.php?categoryphp://filter/convert.base64-encode/resourcei…...
Windows下用Rclone挂载WebDAV的完整指南:从安装到开机自启(含常见问题解决)
Windows系统下Rclone挂载WebDAV全流程实战手册 引言:为什么选择Rclone挂载WebDAV? 在日常办公和团队协作中,我们经常需要访问云端存储的文件。WebDAV作为一种基于HTTP协议的文件管理标准,被Nextcloud、OwnCloud等主流网盘广泛支…...
双模型混搭方案:OpenClaw同时接入百川2-13B与Qwen的实操演示
双模型混搭方案:OpenClaw同时接入百川2-13B与Qwen的实操演示 1. 为什么需要多模型混搭? 去年冬天,当我第一次尝试用OpenClaw自动化处理技术文档时,发现一个有趣的现象:同一个模型在不同任务上的表现差异巨大。Qwen在…...
盘点那些提高作物耐盐性的方法(一)
本文内容速览:随着全球气候变化加剧和不合理灌溉的持续影响,土壤次生盐渍化问题日益突出,许多地区的耕地盐碱化程度不断加重。传统手段在应对作物的高盐胁迫时逐渐显现出效果上限——部分作物的耐盐性改良已进入平台期,单纯依靠农…...
DeepSeek-OCR 2技术突破:动态视觉token重排效果展示
DeepSeek-OCR 2技术突破:动态视觉token重排效果展示 1. 引言 想象一下,当你阅读一份复杂的学术论文时,眼睛不会机械地从左上角扫到右下角,而是会自然地跳过标题、关注图表、追踪公式推导,甚至在不同的文本栏之间灵活…...
塔罗牌选框架:准确率超机器学习模型
技术选型困境与创新突破在软件测试领域,技术栈选择一直是核心挑战。传统方法依赖历史数据和机器学习模型,但常陷入“预测陷阱”——过度依赖过往经验导致创新盲区。例如,自动化测试框架的错误选型每年造成巨额损失:38.7%源于技术生…...
收藏必备!小白程序员快速入门大模型:RAG技术演进全景图
本文介绍了检索增强生成(RAG)技术的演进历程,从基础范式到代码RAG的现状与挑战。文章涵盖了朴素RAG的局限性、语义增强范式、多模态融合、上下文感知以及代码RAG的核心难点与应对策略。此外,还探讨了RAG作为智能体核心记忆与知识子…...
【综述型文章】人工智能驱动的生物医学多模态数据融合与分析中的挑战
论文总结1、作者总结了挑战:1)数据的挑战-meta元学习和transfering learning迁移学习;2)生物医学模型的可解释性--基于网络结构的可解释性(将通路先验信息等加入到网络结构中,约束网络学习参数)…...
Oracle RAC实战:5分钟搞懂SCAN IP和VIP的区别与配置技巧
Oracle RAC实战:SCAN IP与VIP的深度解析与高效配置指南 引言 在Oracle RAC(Real Application Clusters)环境中,高可用性和负载均衡是核心诉求。SCAN IP和VIP作为两大关键技术组件,常常让刚接触RAC的DBA感到困惑。它们虽…...
LibreOffice无界面转换实战:用Python在Linux服务器实现DOCX批量转PDF
LibreOffice无界面转换实战:用Python在Linux服务器实现DOCX批量转PDF 在当今企业级文档处理流程中,自动化转换办公文档格式已成为提升效率的关键环节。对于部署在Linux服务器上的文档处理系统而言,如何在不依赖图形界面的情况下,稳…...
Qt安卓开发实战:从红米K60调试到多机型适配指南
1. Qt安卓开发环境准备 搞Qt安卓开发,首先得把环境搭好。这里假设你已经按照官方文档或者教程配置好了Qt Creator和Android SDK/NDK。如果还没搞定,建议先去Qt官网把Android开发套件下载齐全,包括: Qt for Android(建议…...
