B - The Suspects ——并查集

た入场券 2022-06-12 11:36 147阅读 0赞

Think:  
1知识点：并查集  
2思考：可否过程运行中得到每一个集合的元素数目

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 3e4 + 4;
    
    int n, m, f[N];
    
    void Init();
    int get_f(int x);
    void Merge(int u, int v);
    
    int main(){
        int i, k, u, v, ans;
        while(scanf("%d %d", &n, &m) && (n != 0 || m != 0)){
            ans = 0;
            Init();
            while(m--){
                scanf("%d", &k);
                if(k)
                    scanf("%d", &u);
                for(i = 1; i < k; i++){
                    scanf("%d", &v);
                    Merge(u, v);
                }
            }
            for(i = 0; i < n; i++){
                if(get_f(i) == get_f(0))
                    ans++;
            }
            printf("%d\n", ans);
        }
        return 0;
    }
    void Init(){
        for(int i = 0; i < n; i++)
            f[i] = i;
    }
    void Merge(int u, int v){
        int t1 = get_f(u);
        int t2 = get_f(v);
        f[t2] = t1;
    }
    int get_f(int x){
        if(f[x] == x)
            return f[x];
        else {
            f[x] = get_f(f[x]);
            return f[x];
        }
    }

[vjudge]: https://vjudge.net/contest/163007#problem/B

发表评论取消回复

表情：

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

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

相关阅读

相关 HrbustOJ B - 病毒【并查集】

B - 病毒 Time Limit: 1000 MS Memory Limit: 65536 KB 64-bit integer IO format: %lld ,

落日映苍穹つ/ 2022年08月19日 13:12/ 0 赞/ 136 阅读

相关 POJ 1611-The Suspects（并查集-同一集合）

The Suspects <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS

小灰灰/ 2022年07月11日 05:53/ 0 赞/ 121 阅读

相关 B - The Suspects ——并查集

Think: 1知识点：并查集 2思考：可否过程运行中得到每一个集合的元素数目 [vjudge题目链接][vjudge] 以下为Accepted代码 in

た入场券/ 2022年06月12日 11:36/ 0 赞/ 148 阅读

相关 The Suspects

The Suspects <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS

Bertha 。/ 2022年06月01日 04:17/ 0 赞/ 126 阅读

相关 POJ - 1611 The Suspects （并查集）

The Suspects Description Severe acute resp

短命女/ 2022年05月17日 05:45/ 0 赞/ 134 阅读

相关 POJ 1611 The Suspects——————并查集

The Suspects <table> <tbody> <tr> <td> <div> Language:Default

谁借莪１个温暖的怀抱￠/ 2022年05月16日 06:34/ 0 赞/ 130 阅读

相关并查集-POJ 1611-The Suspects

并查集-POJ 1611-The Suspects -------------------- 题目链接：[The Suspects][] 并查集

左手的ㄟ右手/ 2022年05月15日 01:58/ 0 赞/ 159 阅读

相关（求某个集合中元素的个数-基础并查集）poj1611 The Suspects

传送门：[poj1611 The Suspects][] include<iostream> include<cstdio> include<cmat

不念不忘少年蓝@/ 2022年04月15日 00:49/ 0 赞/ 137 阅读

相关【并查集】Gym - 101128B - Black Vienna

有26张牌（A~Z），其中三张被拿走了。其余23张被分发给了两个人。给你m次调查结果，一次调查结果是对其中一个人询问一对牌，他会告诉你他有这对牌的几张（0~2）。问你有多少种被

约定不等于承诺〃/ 2022年01月07日 01:19/ 0 赞/ 125 阅读

相关 The Suspects 【并查集】超详细题解

目录 1.题目 2.题意 3.思路 4.代码 1.题目严重

阳光穿透心脏的1/2处/ 2021年08月29日 18:18/ 0 赞/ 305 阅读