L2-024. 部落-PAT团体程序设计天梯赛GPLT(tarjan缩点)

题解: 

  可能有人在多个圈子,那么这几个圈子合并为一个部落,一个做法就是将圈子转化为有向图,最后求出的缩点就是部落个数。再查询是否在一个缩点当中。

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 1e18
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin()+1,a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n' 
#define safe_map unordered_map<int, int, custom_hash>
using namespace std;
typedef pair<int,int>pii;
const int N =1e4+7;
struct custom_hash {
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
x ^= FIXED_RANDOM;
return x ^ (x >> 16);
  }
};
vct<int>e[N];
int low[N],dfn[N],tot,cnt;
int scc[N];
bool vis[N];
stack<int>stk;
void tarjan(int x){
  low[x]=dfn[x]=++tot;
  stk.push(x);
  vis[x]=1;
  for(auto t: e[x]){
    if(!dfn[t]){
      tarjan(t);
      mmin(low[x],low[t]);
    }
    else if(vis[t]){
      mmin(low[x],dfn[t]);
    }
  }
  if(low[x]==dfn[x]){
    int y;cnt++;
    do{
      y=stk.top();stk.pop();
      vis[y]=0;
      scc[y]=cnt;
    }while(y!=x);
  }
}
signed main()
{IOS
int X;cin>>X;
set<int>all;
while(X--){
  int n;cin>>n;
  vct<int>a(n+1);
  for(int i=0;i<n;i++){
    cin>>a[i];
    all.insert(a[i]);
  }
  a[n]=a[0];
  for(int i=0;i<n;i++){
    e[a[i]].pb(a[i+1]);
  }
}
int n=all.size();
cout<<n<<" ";
for(int i=1;i<=n;i++){
  if(!dfn[i])tarjan(i);
}
cout<<cnt<<endl;
int q;cin>>q;
while(q--){
  int x,y;cin>>x>>y;
  if(scc[x]==scc[y])cout<<"Y\n";
  else cout<<"N\n";
}
return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/552006.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

BackTrader 中文文档(十二)

原文&#xff1a;www.backtrader.com/ Visual Chart 原文&#xff1a;www.backtrader.com/docu/live/vc/vc/ 与 Visual Chart 的集成支持两者&#xff1a; 实时数据提供 实时交易 Visual Chart是完整的交易解决方案&#xff1a; 在单个平台上集成图表、数据源和经纪功能 更多…

【在线OJ系统】自定义注解实现自增ID的无感插入

实现思路 首先自定义参数注解&#xff0c;然后根据AOP思想&#xff0c;找到该注解作用的切点&#xff0c;也就是mapper层对于mapper层的接口在执行前都会执行该aop操作&#xff1a;获取到对于的方法对象&#xff0c;根据方法对象获取参数列表&#xff0c;根据参数列表判断某个…

时序分解 | Matlab实现WOA-VMD鲸鱼算法WOA优化VMD变分模态分解

时序分解 | Matlab实现WOA-VMD鲸鱼算法WOA优化VMD变分模态分解 目录 时序分解 | Matlab实现WOA-VMD鲸鱼算法WOA优化VMD变分模态分解效果一览基本介绍程序设计参考资料 效果一览 基本介绍 Matlab实现WOA-VMD鲸鱼算法WOA优化VMD变分模态分解&#xff08;完整源码和数据) 1.利用鲸…

Semaphore信号量源码解读与使用

&#x1f3f7;️个人主页&#xff1a;牵着猫散步的鼠鼠 &#x1f3f7;️系列专栏&#xff1a;Java全栈-专栏 &#x1f3f7;️个人学习笔记&#xff0c;若有缺误&#xff0c;欢迎评论区指正 目录 1. 前言 2. 什么是Semaphore&#xff1f; 3. Semaphore源码解读 3.1 acquire…

Linux系统的引导过程与服务控制

目录 一、Linux操作系统引导过程 二、Linux系统服务控制 系统初始化进程 三、运行级别切换 *运行级别及切换 Linux系统的运行级别 四、优化开机自动加载服务 五、修复MBR扇区故障 一、Linux操作系统引导过程 主要步骤 开机自检&#xff1a; 检测硬件设备&#…

C++从入门到精通——const与取地址重载

const与取地址重载 前言一、const正常用法const成员函数问题const对象可以调用非const成员函数吗非const对象可以调用const成员函数吗const成员函数内可以调用其它的非const成员函数吗非const成员函数内可以调用其它的const成员函数吗总结 二、取地址及const取地址操作符重载概…

小米汽车SU7隐藏款曝光!新配色和透明车身亮了 coreldraw教程入门零基础 coreldraw下载 coreldraw2024

刘强东说&#xff0c;论营销&#xff0c;没有任何人能比得过小米。 小米SU7发布会24小时&#xff0c;下定量就超过了蔚来汽车2023年四季度的交付量。 ▲雷军发布的小米SU7 24小时订单量 小米SU7发布会后五天&#xff0c;雷军在北京亦庄工厂亲自交付了第一批创世版本小米SU7&a…

黑马点评(四) -- 分布式锁

1 . 分布式锁基本原理和实现方式对比 分布式锁&#xff1a;满足分布式系统或集群模式下多进程可见并且互斥的锁。 分布式锁的核心思想就是让大家都使用同一把锁&#xff0c;只要大家使用的是同一把锁&#xff0c;那么我们就能锁住线程&#xff0c;不让线程进行&#xff0c;让…

gpt4.0人工智能网页版

在最新的AI基准测试中&#xff0c;OpenAI几天前刚刚发布的GPT-4-Turbo-2024-04-09版本&#xff0c;大幅超越了Claude3 Opus&#xff0c;重新夺回了全球第一的AI王座。 GPT-4-Turbo-2024-04-09版本是目前国内外最强的大模型&#xff0c;官网需要20美元每月才能使用&#xff0c;…

【UE5.1】使用MySQL and MariaDB Integration插件——(3)表格形式显示数据

在上一篇&#xff08;【UE5.1】使用MySQL and MariaDB Integration插件——&#xff08;2&#xff09;查询&#xff09;基础上继续实现以表格形式显示查询到的数据的功能 效果 步骤 1. 在“WBP_Query”中将多行文本框替换未网格面板控件&#xff0c;该控件可以用表格形式布局…

Pytest测试用例中的mark用法(包含代码示例与使用场景详解)

在软件开发中&#xff0c;测试是确保代码质量和功能稳定性的重要环节。Python作为一门流行的编程语言&#xff0c;拥有丰富的测试工具和框架&#xff0c;其中pytest是其中之一。pytest提供了丰富的功能来简化测试用例的编写&#xff0c;其中的mark功能允许我们对测试用例进行标…

理解思维链Chain of Thought(CoT)

Chain of Thought&#xff08;CoT&#xff09;&#xff0c;即“思维链”&#xff0c;是人工智能领域中的一个概念&#xff0c;特别是在自然语言处理和推理任务中。它指的是一种推理过程&#xff0c;其中模型在生成最终答案之前&#xff0c;先逐步推导出一系列的中间步骤或子目标…

【日常记录】【CSS】SASS循环的使用

文章目录 1、引言2、安装3、举例4、参考链接 1、引言 目前在任何项目框架中&#xff0c;都会有css 预处理器&#xff0c;目前一般使用 sass、less 这俩其中之一&#xff0c;它可以简化css的书写 Sass 是一款强化 CSS 的辅助工具&#xff0c;它在 CSS 语法的基础上增加了变量 (v…

推动企业档案数字化转型的措施

推动企业档案数字化转型的措施有以下几点&#xff1a; 1. 制定数字化转型战略&#xff1a;企业应该制定明确的数字化转型战略&#xff0c;明确企业数字化转型的目标、步骤和时间表&#xff0c;并将档案数字化转型作为其中的重要内容。 2. 投资数字化技术&#xff1a;企业应该投…

代码随想录:二叉树5(层序遍历全解)

目录 102.二叉树的层序遍历 107.二叉树的层序遍历II 199.二叉树的右视图 637.二叉树的层平均值 429.N叉树的层序遍历 501.在每个树行中找最大值 116.填充每个节点的下一个右侧节点指针 117.填充每个节点的下一个右侧节点指针II 104.二叉树的最大深度 111.二叉树的最大…

UE5 HLSL 详细学习笔记

这里的POSITION是变量Position的语义&#xff0c;告诉寄存器&#xff0c;此变量的保存位置&#xff0c;通常语义用于着色器的输入和输出&#xff0c;以冒号“&#xff1a;”的方式进一步说明此变量&#xff0c;COLOR也类似 还有什么语义呢&#xff1f; HLSL核心函数&#xff1a…

CAN的底层驱动

框架图 拆解链路模型 CAN子系统 can_controller Core 包含协议控制器和接收/发送移位寄存器。它可处理所有 ISO 11898-1: 2015 协议功能,并支持 11 位和 29 位标识符。

【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历)

目录 树和森林树的存储结构一、树的双亲表示法&#xff1a;二、树的孩子表示法方法一&#xff1a;定长结点的多重链表方法二&#xff1a;不定长结点的多重链表方法三&#xff1a;孩子单链表表示法 三、树的二叉链表(孩子-兄弟)存储表示法 森林与二叉树的转换树和森林的遍历先根…

Java中的容器

Java中的容器主要包括以下几类&#xff1a; Collection接口及其子接口/实现类&#xff1a; List 接口及其实现类&#xff1a; ArrayList&#xff1a;基于动态数组实现的列表&#xff0c;支持随机访问&#xff0c;插入和删除元素可能导致大量元素移动。LinkedList&#xff1a;基…

前端常见面试题:HTML+CSS

1. title与h1的区别、b与strong的区别、i与em的区别&#xff1f; title与h1的区别&#xff1a; title标签用于定义整个HTML文档的标题&#xff0c;它显示在浏览器窗口的标题栏或者标签页上。每个HTML文档只应该有一个title标签&#xff0c;它对搜索引擎优化&#xff08;SEO&a…
最新文章