首页 > 其他分享 >P5836 [USACO19DEC] Milk Visits S(树上并查集)

P5836 [USACO19DEC] Milk Visits S(树上并查集)

时间:2024-08-13 12:54:21浏览次数:10  
标签:USACO19DEC int 查集 cin Visits col char fa find

核心思路

对于相同颜色且相邻的点合并。

若不在同一集合,则0

若在同一集合,同色1 异色0

AC 代码

#include <bits/stdc++.h>   
using namespace std;  
int fa[1145141];
char col[1145141];
int n,m;
int find(int x)
{
	if(x==fa[x])	return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
	fa[find(x)]=find(y);
}
int main() {  
    cin >> n >> m;  
    for (int i = 1; i <= n; i++) {  
        char a;
        cin>>a;
        fa[i] = i;
        col[i] = a;
    } 
    for (int i = 1; i < n; i++) {  
        int u, v;  
        cin >> u >> v;  
        if(col[u] == col[v]){
        	merge(u,v);
		}
    }  
    
    for (int i = 0; i < m; i++) {  
        int a, b;  
        char c;
        cin >> a >> b>>c;  
        if(find(a) == find(b)&&col[a] != c){
        	cout<<0;
		}
		else{
			cout<<1;
		}
    }  
  	
    return 0;  
}

标签:USACO19DEC,int,查集,cin,Visits,col,char,fa,find
From: https://blog.csdn.net/2301_77025310/article/details/141157805

相关文章

  • *算法训练(leetcode)第四十七天 | 并查集理论基础、107. 寻找存在的路径
    刷题记录*并查集理论基础107.寻找存在的路径*并查集理论基础讲解107.寻找存在的路径题目地址直接套模板。结点编号从1开始,因此定义father数组时需要n+1个空间,否则会越界。时间复杂度:O(......
  • 广场舞老太太都看得懂的并查集
    1.并查集为什么叫“并查集”这个名字?因为并查集它的主要用处就是并(合并无交集集合)和查(查找元素或判断是否有该元素),当然路径压缩也得用到它。话说回来,并查集虽然是图论里的东西,但是本身像个树。2.算法说到并查集,就不得不提到压缩路径了,它是一个超级简单,但是很牛的算法,算法主......
  • 为什么并查集路径压缩不需要维护rank?
    在基于rank进行优化的并查集中,路径压缩确实不需要维护rank数组。这是因为路径压缩和rank优化有不同的目的和作用机制。让我们详细解释一下原因:Rank优化的目的:Rank优化的主要目的是在合并两个集合时,让较小的树成为较大的树的子树,以保持树的平衡性。这样可以避免树变得过于深,从而......
  • 并查集详解
    并查集并查集是一种树形数据结构,用于处理一些不相交集合的合并及查询问题(即所谓的并、查)。具体详解见此并查集本身是真的太板了。。普及-以下的题基本全是板。直接见例题吧:板子一【模板】并查集题目描述如题,现在有一个并查集,你需要完成合并和查询操作。【】输入格式】第......
  • 数据结构 - 并查集路径压缩
    ......
  • 并查集
    并查集在每个集合中选择一个元素,作为整个集合的代表。使用一个树形结构存储每个集合,树上的每个节点都是一个元素,树根是集合的代表元素。存储时,记录每个节点\(x\)的父亲\(fa[x]\)。查询\(x\)和\(y\)是否在同一集合时,分别从两个点出发,寻找它们的树根。若树根相同,则说明\(......
  • 数据结构 - 并查集基础
    ......
  • 【每日一题】【并查集】【力扣】695.岛屿的最大面积 C++
    力扣695.岛屿的最大面积695.岛屿的最大面积题目描述给你一个大小为m×nm\timesnm×n的二进制矩阵......
  • 树(tree) - 题解(带权并查集)
    树(tree)时间限制:C/C++2000MS,其他语言4000MS内存限制:C/C++256MB,其他语言512MB描述给定一个\(n\)个结点,\(n−1\)条边的有根树。第\(i\)条边可以用(\(a_i,b_i\))来描述,它表示连接结点\(a_i\)和结点\(b_i\)的一条边,其中结点\(a_i\)是结点\(b_i\)的父节点。......
  • 代码随想录算法训练营第57天 | 并查集理论基础
    并查集理论基础https://www.programmercarl.com/kamacoder/图论并查集理论基础.html107.寻找存在的路径https://kamacoder.com/problempage.php?pid=1179代码随想录https://www.programmercarl.com/kamacoder/0107.寻找存在的路径.html#思路并查集理论基础并查集用于判断......