POJ2524 并查集

曾经终败给现在 2021-11-29 17:32 296阅读 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 条评论，296人围观）

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

相关阅读

相关 poj 1182-食物链【并查集】

食物链 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

r囧r小猫/ 2022年08月21日 06:51/ 0 赞/ 164 阅读

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

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

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

相关 POJ2524 并查集应用

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

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

相关 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 赞/ 156 阅读

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

Ubiquitous Religions Description There are so man

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

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

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

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

相关 POJ2524 并查集

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

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

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

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

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

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

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

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

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

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

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