POJ2524 并查集

曾经终败给现在 2021-11-29 17:32 266阅读 0赞

#include<iostream>
    using namespace std;
    int father[50005];
    int rank[50005];
    int maxNum;
    
    void make_set(int x){
        
         father[x]=x;
         rank[x]=1;
    }
    
    int find_set(int x){
        
    if(x!=father[x])
         {
        
             father[x]=find_set(father[x]);
         }
    return father[x];
    }
    
    void Union(int x,int y){
        
        x=find_set(x);
        y=find_set(y);
    if(x==y)  return;
    if(rank[x]<=rank[y]){
        
          father[x]=y;
          rank[y]+=rank[x];
          maxNum--;     //每合并一次总数减一
        }
    else{
        
          father[y]=x;
          rank[x]+=rank[y];
          maxNum--;
        }   
    }
    
    int main(){
        
    int m,n;
    int i,j;
    int x,y;
    int Case=1;
        freopen("acm.txt","r",stdin);
        cin>>n>>m;
    while(n){
        
           maxNum=n;
    for(i=n;i>0;i--)
            make_set(i);
    for(j=m;j>0;j--){
        
            cin>>x>>y;
            Union(x,y);
          }
          cout<<"Case "<<Case<<": "<<maxNum<<endl;
          cin>>n>>m;
          Case++;
          }
    return 0;
    }

转载于:https://www.cnblogs.com/Jason-Damon/archive/2012/01/19/2327419.html

发表评论取消回复

表情：

评论列表（有 0 条评论，266人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 2524 Ubiquitous Religions //简单并查集

Ubiquitous Religions <table> <tbody> <tr> <td><strong>Time Limit:</strong>&nbs

忘是亡心i/ 2022年08月11日 04:28/ 0 赞/ 108 阅读

相关 POJ2524 并查集应用

import java.io.FileNotFoundException; import java.util.Scanner; public

曾经终败给现在/ 2022年06月18日 11:08/ 0 赞/ 139 阅读

相关 POJ 2524 Ubiquitous Religions（水水的并查集）

There are so many different religions in the world today that it is difficult to keep tr

ゞ浴缸里的玫瑰/ 2022年06月11日 08:59/ 0 赞/ 130 阅读

相关 POJ - 2524 Ubiquitous Religions （并查集）

Ubiquitous Religions Description There are so man

比眉伴天荒/ 2022年05月17日 05:44/ 0 赞/ 122 阅读

相关 POJ2524 Ubiquitous Religions ——————并查集

Ubiquitous Religions <table> <tbody> <tr> <td> <div> Language:Def

迈不过友情╰/ 2022年05月16日 06:35/ 0 赞/ 103 阅读

相关 POJ-1182.食物链(并查集)

[1182.食物链][1182.] Description 动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有

蔚落/ 2022年03月07日 01:36/ 0 赞/ 202 阅读

相关 POJ2524 并查集

include<iostream> using namespace std; int father[50005]; int rank[50005

曾经终败给现在/ 2021年11月29日 17:32/ 0 赞/ 267 阅读

相关扩展并查集——POJ - 1182

题目含义找出与之前的话不符的假话的数目题目分析简单的扩展并查集题目代码 include<iostream> include<stdio.h>

桃扇骨/ 2021年11月22日 09:28/ 0 赞/ 233 阅读

相关 POJ—— 2524 Ubiquitous Religions （并查集模板题）

题目链接：[http://poj.org/problem?id=2524][http_poj.org_problem_id_2524] 题目： Ubiquitous

以你之姓@/ 2021年09月26日 11:50/ 0 赞/ 171 阅读

相关 POJ - 2524 Ubiquitous Religions 【并查集】题解

目录 1.题目 2.思路 3.代码 1.题目北理CS学院2015级的学长学姐们终于

淩亂°似流年/ 2021年07月24日 22:12/ 0 赞/ 275 阅读