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

不念不忘少年蓝@ 2022-04-15 00:49 133阅读 0赞

传送门：[poj1611 The Suspects][]

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=30010;
    int par[maxn],n,m;
    
    void init(){
        for(int i=0;i<n;i++)
            par[i]=i;
    }
    
    int fi(int x){
        if(par[x]!=x) return par[x]=fi(par[x]);
        return par[x];
    }
    
    void join(int x,int y){
        int fx=fi(x),fy=fi(y);
        if(fx!=fy){
            par[fy]=fx;
        }
    }
    
    
    int main(){
    	while(~scanf("%d%d",&n,&m)){
    		if(n==0&&m==0) break;
    		 init();
    	    int k,a,b;
    	    while(m--){
    	        scanf("%d",&k);
    	        if(k>0){
    	            scanf("%d",&a);
    	            k--;
    	            while(k--){
    	                scanf("%d",&b);
    	                join(a,b);
    	            }
    	        }
    	    }
    	    int cnt=0;
    	    for(int i=0;i<n;i++){
    	        if(fi(0)==fi(i)) cnt++;
    	    }
    	    printf("%d\n",cnt);
    	}
       
        return 0;
    }

[poj1611 The Suspects]: http://poj.org/problem?id=1611

发表评论取消回复

表情：

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

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

相关阅读

相关畅通工程（并查集之计算集合的子集合的个数）

畅通工程 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Othe

分手后的思念是犯贱/ 2022年08月07日 10:47/ 0 赞/ 113 阅读

相关 <poj-1611>The Suspects

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

忘是亡心i/ 2022年07月15日 08:56/ 0 赞/ 125 阅读

相关 B - The Suspects ——并查集

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

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

相关 POJ - 1611 - The Suspects

-------------------- 题目连接：[http://poj.org/problem?id=1611][http_poj.org_problem_id_1611

柔光的暖阳◎/ 2022年06月10日 00:09/ 0 赞/ 152 阅读

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

The Suspects Description Severe acute resp

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

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

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

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

相关并查集-POJ 1611-The Suspects

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

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

相关 POJ-1611—The Suspects

[1611–The Suspects][1611_The Suspects] Description Severe acute respiratory syndro

客官°小女子只卖身不卖艺/ 2022年03月09日 01:10/ 0 赞/ 178 阅读

相关 POJ2524 并查集

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

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

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

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

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