首页 > 其他分享 >并查集(反集)进阶 P1892 [BOI2003] 团伙

并查集(反集)进阶 P1892 [BOI2003] 团伙

时间:2024-03-25 20:31:46浏览次数:18  
标签:opt 反集 进阶 int 查集 整数 朋友 敌人 输入

现在有 n 个人,他们之间有两种关系:朋友和敌人。我们知道:

  • 一个人的朋友的朋友是朋友
  • 一个人的敌人的敌人是朋友

现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。

输入格式

第一行输入一个整数 n 代表人数。

第二行输入一个整数 m 表示接下来要列出 m 个关系。

接下来 m 行,每行一个字符 opt 和两个整数 p,q,分别代表关系(朋友或敌人),有关系的两个人之中的第一个人和第二个人。其中opt 有两种可能:

  • 如果 opt 为 F,则表明 p 和 q 是朋友。
  • 如果 opt 为 E,则表明 p 和 q 是敌人。

输出格式

一行一个整数代表最多的团体数。

输入输出样例

输入 #1

6
4
E 1 4
F 3 5
F 4 6
E 1 2

输出 #1

3

说明/提示

对于 100%100% 的数据,2≤n≤1000,1≤m≤5000,1≤p,q≤n。

#include<iostream>
using namespace std;
const int N=10010;
int p[N];
int find(int x)
{
    if(p[x]!=x)
    {
        p[x]=find(p[x]);
    }
    return p[x];
}
int main()
{
    int n;
    cin>&g

标签:opt,反集,进阶,int,查集,整数,朋友,敌人,输入
From: https://blog.csdn.net/2303_80209427/article/details/137024684

相关文章

  • 蓝桥杯算法集训 - Week 4:BFS、并查集、Flood Fill、哈希、单调栈/队列
    蓝桥杯算法集训-Week4本系列随笔用于整理AcWing题单——《蓝桥杯集训·每日一题2024》的系列题型及其对应的算法模板。一、BFSBFS算法复习参考:BFS(Java)广度优先搜索简单介绍、模板、案例(一)Ⅰ、代码模板staticvoidbfs(Troot){//双端队列,用来存储元素D......
  • Java String类深入了解JDK各个版本进阶版本
    JavaString类深入了解JDK各个版本进阶版本一,底层类型在jdk11中Stringvalue存储字符串值是byte[]数组,String中存储字节码的是coder也是byte类型,因此String的底层数据存储类型成为了byte类型而在jdk8中String的Stringvalue存储字符串值是char[]数组,因此因此可......
  • nginx进阶-3(32-34天)学习笔记
    nginx进阶-3(33-34天)学习笔记知识回顾1.nginx部署单机网站2.nginx部署多个网站3.nginx访问方式4.nginx安全5.nginx加密访问实战00---nginx企业实战1.nginx搭建一个文件共享供用户下载的服务器#步骤1.配置nginx文件cd/usr/local/nginx/conf/vhostvibbs.conf......
  • 【进阶五】Python实现SDVRP(需求拆分)常见求解算法——自适应大邻域算法(ALNS)
    基于python语言,采用经典自适应大邻域算法(ALNS)对需求拆分车辆路径规划问题(SDVRP)进行求解。目录往期优质资源1.适用场景2.代码调整3.求解结果4.代码片段参考往期优质资源经过一年多的创作,目前已经成熟的代码列举如下,如有需求可私信联系,表明需要的问题与算法......
  • Go语言进阶:深入理解深拷贝与浅拷贝
    Go语言进阶:深入理解深拷贝与浅拷贝原创 lipeilun 海天二路搬砖工 2024-03-1719:01 福建 听全文一、引言在Go语言的编程实践中,内存管理和数据复制是经常遇到的问题。特别是在处理复杂数据结构或自定义类型时,如何正确、高效地复制数据变得尤为重要。深拷贝与浅拷贝是......
  • Android14音频进阶:AudioFlinger究竟如何混音?(六十三)
    简介:CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长!优质专栏:Audio工程师进阶系列【原创干货持续更新中……】......
  • 【Python学习】——函数进阶
    零、函数基础在之前的文章里:【Python学习】——基础语法一、多返回值deftest_return():    return1,2x,y=test_return()print(x) #结果1print(y) #结果2按照返回值的顺序,写对应顺序的多个变量接受即可变量之间用逗号隔开支持不同类型的数据return......
  • C语言进阶——动态内存管理
    目录一、C语言底层内存知识补充二、动态内存函数1.1free1.2malloc1.3calloc1.4realloc三、使用常见错误3.1对非动态开辟内存使用free释放3.2空指针未判断造成的错误3.3使用free释放一块动态开辟内存的一部分3.4对同一块动态内存多次释放3.5动态开辟内存没有释放而......
  • 并查集
    并查集畅通工程某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?Input测试输入包含若干测试......
  • 摸爬滚打半年,我是如何从小白进阶到渗透测试工程师
    前言工作也好几年了,在这摸爬滚打中,遇到了服务器被黑,网站被人DDOS攻击,数据库被篡改等等。服务器也不是你说不让人上就不让人上的,所以IT安全这个话题还是比较沉重的,涉及的东西很多,只有你了解得更多,你才会知道你所了解的安全其实是那么少。【点此开始渗透学习】梦想的开始......