首页 > 其他分享 >洛谷 P1892 [BOI2003] 团伙

洛谷 P1892 [BOI2003] 团伙

时间:2024-09-11 16:03:25浏览次数:12  
标签:洛谷 int P1892 fa add BOI2003 else find

P1892 [BOI2003] 团伙

种类并查集!!!!

存敌人

主要要理解敌人的敌人就是朋友这句话,我们就可以用并查集来维护朋友,用一个数组来储存他的其中一个敌人,后面遇到其他他的敌人时,将他的敌人用并查集连起来成为朋友。

注意这题要你输出团队数而不是团队的人数不会就我这么唐吧

#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m;

int fa[N];
int a[N];

int find(int x){
	return fa[x]==x?x:find(fa[x]);
}

void add(int u,int v){
	int x=find(u);
	int y=find(v);
	fa[x]=y;
}

int cnt[1005];
int ans;

int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		char c;
		int u,v;
		cin>>c>>u>>v;
		if(c=='F'){
			add(u,v);
		}
		else{
			if(!a[u]){
				a[u]=v;
			}
			else{
				add(a[u],v);
			}
			if(!a[v]){
				a[v]=u;
			}
			else{
				add(a[v],u);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(fa[i]==i){
			ans++;
		}
	}
	cout<<ans;
    return 0; 
}

反集

当然这题的方法开两倍空间进行维护,或者说叫反集。

#include <bits/stdc++.h>
using namespace std;
const int N=2005;
int n,m;
int fa[N];
int find(int x){
	return fa[x]==x?x:find(fa[x]);
}
void add(int u,int v){
	int x=find(u);
	int y=find(v);
	fa[x]=y;
}
int ans;
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n*2;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		char c;
		int u,v;
		cin>>c>>u>>v;
		if(c=='F'){
			add(u,v);
		}	
		else{
			add(u+n,v);
			add(v+n,u);
		}
	} 

	for(int i=1;i<=n;i++){
		if(fa[i]==i){
			ans++;
		}
	}
	cout<<ans;
    return 0; 
}

标签:洛谷,int,P1892,fa,add,BOI2003,else,find
From: https://www.cnblogs.com/sadlin/p/18408381

相关文章

  • 洛谷题单指南-分治与倍增-P1908 逆序对
    原题链接:https://www.luogu.com.cn/problem/P1908题意解读:求序列逆序对数。解题思路:1、暴力法对于每一个数,寻找后面有多少数比其小,或者采用冒泡排序,交换的次数即逆序对的个数,复杂度为O(n^2)2、归并排序法在归并排序过程中,会进行有序序列的合并,设两部分连续的有序序列为a[s1,......
  • 【洛谷 P5076】【深基16.例7】普通二叉树(简化版)题解(多重集合+lower_bound+upper_bound
    【深基16.例7】普通二叉树(简化版)题目描述您需要写一种数据结构,来维护一些数(都是以内的数字)的集合,最开始时集合是空的。其中需要提供以下操作,操作次数不超过:查询数的排名(排名定义为比当前数小的数的个数。若有多个相同的数,应输出最小的排名)。查询排名为的数。求的前驱(......
  • 洛谷题单指南-分治与倍增-P1177 【模板】归并排序
    原题链接:https://www.luogu.com.cn/problem/P1177题意解读:归并排序模版题。解题思路:第一步:确定分界点。mid=(l+r)/2第二步:排序。对左右两边递归排序第三步:归并。合并左右两边排序好的内容关键在第三步:通过双指针对两个有序数组进行合并100分代码:#include<bits/std......
  • 挑战不可能篇1——洛谷28分钟14道CCF GESP C++ 一级上机题&洛谷14道题题解
    扯谈今天继续挑战不可能:洛谷28分钟14道题这我个人认为不简单,算上编译、提交、命名等杂七杂八的东东之后,只剩下了大约1分钟/题。本次挑战的是CCFGESPC++一级上机题.这竟然能成功!下面附上每一题第一题第二题第三题第四题第五题第六题第七题第八题第九题第十题......
  • 洛谷题单指南-常见优化技巧-P1714 切蛋糕
    原题链接:https://www.luogu.com.cn/problem/P1714题意解读:求长度不超过m的最大子段和解题思路:1、暴力法设a[N]表示原数组,s[N]是a[N]的前缀和,对于每一个元素s[i],计算其与前m个元素之差,取差值最大值,用代码表示:for(inti=1;i<=n;i++){for(intj=i-1;j>=i-m......
  • 洛谷题单指南-常见优化技巧-P2880 [USACO07JAN] Balanced Lineup G
    原题链接:https://www.luogu.com.cn/problem/P2880题意解读:在若干个不定长区间里,求区间最大值与最小值之差解题思路:对于区间求最值,通常有几种方式:1、暴力法,通过枚举所有的区间来计算区间最值2、单调队列,针对区间长度固定的情况3、ST表,针对区间长度不固定且元素不会发生改变的......
  • 洛谷题单指南-常见优化技巧-P1886 滑动窗口 /【模板】单调队列
    原题链接:https://www.luogu.com.cn/problem/P1886题意解读:单调队列模版题。解题思路:采用双端队列维护单调的序列,单调队列三部曲:1、去头,当窗口内元素个数超过k,队头出队2、去尾,当要加入的元素会破坏单调性,队尾出队3、入队,将元素的下标存入队列每一次入队后,队头元素即为窗口最......
  • 【洛谷 P1996】约瑟夫问题 题解(数组+模拟+循环)
    约瑟夫问题题目描述个人围成一圈,从第一个人开始报数,数到的人出列,再由下一个人重新从开始报数,数到的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰名小朋友,而该题是全部出圈。输入......
  • 洛谷 P9754 [CSP-S 2023] 结构体 题解
    题目传送门洛谷博客CSDNCSP-S2023T3结构体题解基本思路本题主要考查编码能力,所以直接给出基本思路:由于可以递归式的创建元素,最多可以同时存在\(100^{100}\)个不同的基础类型的元素。即使算上最大地址的限制,元素的数量也能达到\(10^{18}\)。显然,依次构造每个元素,在空......
  • 【洛谷P5587】打字练习
    【P5587】打字练习【废话】首先,作为我练习字符串的一道题,很自然的意料之中的遇到了瓶颈【前置知识】字符的输入  久远的记忆让我以为gets还能用,于是就RE了,后来又用scanf("%[^\n]",s);,但是由于没有熟练掌握,换为getchar    getchar一次只能进行一个字符的......