`

数据结构 并查集——poj 2524

阅读更多

题目描述:

     世界上宗教何其多。假设你对自己学校的学生总共有多少种宗教信仰很感兴趣。学校有n个学生,但是你不能直接问学生的信仰,不然他会感到很不舒服的。有另外一个方法是问m对同学,是否信仰同一宗教。根据这些数据,相信聪明的你是能够计算学校最多有多少种宗教信仰的。(好,不罗嗦那么多了)

  解题思路---->显然并查集了。并查集的详细解释在可以点击 并查集(不相交集合)进行学习。思路可以很清晰的,一开始假设大家都各自信仰一个宗教,那么总的数目ans就是学生数目,每当发现有一对学生信仰同一个宗教,那么ans--;

#include <stdio.h>
#include <iostream>
using namespace std;

const int MAXN = 50005; /*结点数目上线*/
int pa[MAXN];    /*p[x]表示x的父节点*/
int rank[MAXN];    /*rank[x]是x的高度的一个上界*/
int n, ans; 

void make_set(int x)
{/*创建一个单元集*/
    pa[x] = x;
    rank[x] = 0;
}

int find_set(int x)
{/*带路径压缩的查找*/
    if(x != pa[x])
        pa[x] = find_set(pa[x]);
    return pa[x];
}

/*按秩合并x,y所在的集合*/
void union_set(int x, int y)
{
    x = find_set(x);
    y = find_set(y);
    if(x == y)return ;
    ans--;    //统计
    if(rank[x] > rank[y])/*让rank比较高的作为父结点*/
    {
        pa[y] = x;
    }
    else 
    {
        pa[x] = y;
        if(rank[x] == rank[y])
            rank[y]++;
    }
}
//answer to 2524
int main()
{
    int m, i, j = 1, x, y;
    while(scanf("%d%d", &n, &m))
    {
        if(n == m && m == 0) break;
        for(i = 1; i <= n; i++)
            make_set(i);
        ans = n;
        for(i = 0; i < m; i++)
        {
            scanf("%d%d", &x, &y);
            union_set(x, y);
        }
        printf("Case %d: %d\n", j, ans);
        j++;
    }
    return 0;
}

 

分享到:
评论

相关推荐

    poj2492并查集应用的扩展

    poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处

    POJ 1988 简单并查集,

    并查集是一种用于处理一些不交集的合并及查询问题的数据结构,它支持两种基本操作:合并两个集合(`union`)和查找一个元素所在的集合(`find`)。并查集通常用于解决连通性问题,如图中的顶点是否相连、网络中的...

    晒代码之一——POJ3469第一次AC

    这题是道神题,神就神在,它既能让你搞懂网络流及其优化,还给了你很大的优化空间。

    数据结构--并查集(Union-Find Sets)

    并查集(Union-Find Sets)是数据结构中一种用于管理元素集合的高效算法,它主要处理两个操作:连接(union)与查找(find)。在并查集中,元素被分到不同的集合中,每个集合代表一个独立的组件。连接操作将两个元素...

    并查集问题

    1. poj2524.cpp:这是一个POJ(Problem Setter's Online Judge)的编程题目,通常涉及到特定的算法问题,可能需要利用并查集解决连通性或路径查找问题。 2. hdoj1233最小生成树,克鲁斯卡尔.cpp:最小生成树是图论...

    数据结构中poj题目算法分类——针对ACM竞赛

    学习这些数据结构和算法,并通过实践poj题目来加深理解,是提高ACM竞赛能力的关键步骤。通过初级到高级的题目练习,参赛者能够逐步提升解决问题的能力,应对复杂的编程挑战。在实战中,理解和熟练运用这些知识点,将...

    中缀表达式的值——C++poj原题

    北京大学数据结构与算法课程作业代码,供广大学习c++的同学参考与学习

    POJ 1006 源代码——中国剩余定理分析

    POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析

    虫子的生活——C++poj原题

    北京大学数据结构与算法课程作业代码,供广大学习c++的同学参考与学习

    1089_bingchaji.rar_1089_bingchaji.rar _并查集

    并查集是一种在图论和数据结构中广泛使用的算法,主要用来处理一些不相交集合的合并与查询问题。在给定的标题“1089_bingchaji.rar_1089_bingchaji.rar _并查集”和描述“POJ1089 并查集可以解决 并查集加路径压缩”...

    并查集C++实现

    这份代码用C++实现了经典算法并查集,来源于poj题目1182

    POJ1011-Sticks

    一种常见的方法是使用深度优先搜索(DFS)或广度优先搜索(BFS)来构建线段之间的连接,并通过并查集(Disjoint Set)数据结构来判断是否存在不相交的集合。 1. **数据结构**:首先,我们需要用数组或者链表存储...

    并查集总结

    并查集,作为数据结构的一种,主要用于处理一系列的合并及查询问题,特别是在处理大量节点间的连通性问题上表现出色。下面将详细解析并查集的原理、应用场景、以及优化技巧,结合具体代码实例,帮助读者更深入地理解...

    并查集(Union Find set)基础

    并查集基础 acm 算法 poj oi 并查集基础.ppt

    POJ算法题目分类

    数据结构是指解决问题的数据结构,包括串、排序、简单并查集、哈希表和二分查找等高效查找法、哈夫曼树、堆、trie 树等。 * 串:串是指解决问题的基本数据结构,如 poj1035、poj3080、poj1936。 * 排序:排序是指...

    poj2488——dfs深度优先遍历

    poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历

    acm poj300题分层训练

    poj1035、poj3080等训练了串的操作,poj2388、poj2299等则涉及排序问题,poj2524、poj1611等是并查集的实例,poj3349、poj3274等展示了哈希表和二分查找,poj3253是哈夫曼树的题目,poj2442和poj1442则关于堆。...

    北大POJ初级题-数据结构:解题报告+AC代码

    北京大学在线判题系统POJ(Problem Online Judge)是许多编程爱好者和学习者锻炼算法技能的平台,特别是对于初学者,它提供了很多基础题目来帮助理解并应用数据结构。本资源包含的是北大POJ初级题目的解题报告以及...

    poj经典数据结构题目解题报告

    在ACM竞赛中,Poj平台上的数据结构题目常常考验选手对算法的深入理解和高效实现。本篇解题报告主要探讨了Pku ACM 3253 Fence Repair问题,这是一道涉及哈夫曼编码(Huffman Coding)的题目。哈夫曼编码是一种用于...

Global site tag (gtag.js) - Google Analytics