4.3算法之图论 1526:宗教信仰 并查集模板题

http://noi.openjudge.cn/ch0403/1526/

思路

并查集模板题

源码

//
//  1526.cpp
//  test
//
//  Created by bytedance on 2020/7/28.
//  Copyright © 2020 bytedance. All rights reserved.
//

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

vector<int> father;

int find(int x){
    return x==father[x]?x:find(father[x]);
}
void un(int x,int y){
    int fx = find(x);
    int fy = find(y);
    if(fx>fy){
        father[fy]=fx;
    }else{
        father[fx]=fy;
    }
}
int main(){
    int m,n;
    int idx=0;
    while(cin>>n>>m){
        idx++;
        if(n==0&&m==0)break;
        father.clear();
        for(int i = 0;i <=n;++i){
            father.push_back(i);
        }
        while(m--){
            int a,b;
            cin >> a>>b;
            un(a,b);
        }
        int res = 0;
        for(int i = 1;i <=n;++i){
            if(find(i)==i){
                res++;
            }
        }
        cout<<"Case "<< idx<<": "<<res<<endl;
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注