HDU 1213 How Many Tables (dfs求联通块 || 并查集)

灰太狼 2024-02-17 19:45 14阅读 0赞

这题真打脸，比赛的时候愣是没写出来（因为当天写了蓝桥杯上的历届试题--剪格子，这题数据很水，被搞晕了），现在回过头来看看，很简单，就是单纯找联通块，。

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=1000+10;
    int g[maxn][maxn];
    int vis[maxn];
    int n,m;
    
    void dfs(int i){
    	for(int j=1;j<=n;j++){
    		if(g[i][j] && !vis[j]){
    		vis[j]=1;
    		dfs(j);		
    		}
    	}
    }
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d%d",&n,&m);
    		memset(g,0,sizeof(g));
    		for(int i=0;i<m;i++){
    			int a,b;
    			scanf("%d%d",&a,&b);
    			g[a][b]=g[b][a]= 1;
    		}
    		
    		memset(vis,0,sizeof(vis));
    		int cnt=0;
    		for(int i=1;i<=n;i++){
    			if(!vis[i])
    			{
    			vis[i]=1;
    			dfs(i);	
    			cnt++;
    		     }
    			}
    		printf("%d\n",cnt);
    	}
    	return 0;
    }

并查集：

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=1000;
    int pre[maxn];
    int N,M;
    int tol;
    
    int find(int x){
    	return pre[x]==x?x:find(pre[x]);
    }
    
    void Union(int a,int b){
      int fx=find(a),fy=find(b);
      if(fx!=fy){
      	tol++;
      	pre[fx]=fy;	
      }	
    }
    
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d%d",&N,&M);
    		
    		tol=0;
    		
    		for(int i=1;i<=N;i++)
    		  pre[i]=i;
    		  
    		for(int i=0;i<M;i++){
    			int a,b;
    			scanf("%d%d",&a,&b);
    			Union(a,b);
    		}
    		
    		printf("%d\n",N-tol);
    	}
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 HDU 1213 How Many Tables (dfs求联通块 || 并查集)

这题真打脸，比赛的时候愣是没写出来（因为当天写了蓝桥杯上的历届试题--剪格子，这题数据很水，被搞晕了），现在回过头来看看，很简单，就是单纯找联通块，。 AC代码：

灰太狼/ 2024年02月17日 19:45/ 0 赞/ 15 阅读

相关 HDU 1213 How Many Tables (并查集炒鸡入门题)

Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius

梦里梦外;/ 2022年06月13日 13:50/ 0 赞/ 180 阅读

相关 hdu 1213 How Many Tables（并查集水题）

题目： Today is Ignatius’ birthday. He invites a lot of friends. Now it’s dinner time. Ig

我会带着你远行/ 2022年06月10日 12:23/ 0 赞/ 165 阅读

相关 HDU - 1213 - How Many Tables

-------------------- 题目连接：[http://acm.hdu.edu.cn/showproblem.php?pid=1213][http_acm.hdu

梦里梦外;/ 2022年06月10日 00:09/ 0 赞/ 149 阅读

相关并查集 hdu1213 How Many Table 图论500题

How Many Tables Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J

秒速五厘米/ 2022年06月06日 12:35/ 0 赞/ 191 阅读

相关 HDU 1213 How Many Tables (并查集)

//题意自己看，不会度娘 include <stdio.h> include <string.h> int a[1050]; int

一时失言乱红尘/ 2022年06月05日 01:55/ 0 赞/ 160 阅读

相关并查集 HDU__1213 How Many Tables

How Many Tables Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J

左手的ㄟ右手/ 2022年05月26日 06:54/ 0 赞/ 93 阅读

相关 HDU - 1213 How Many Tables （并查集）

How Many Tables Problem Description Today is

╰+攻爆jí腚メ/ 2022年05月17日 05:46/ 0 赞/ 159 阅读

相关并查集-HDU 1213-How Many Tables

并查集-HDU 1213-How Many Tables -------------------- 题目链接：[How Many Tables][]

深藏阁楼爱情的钟/ 2022年05月15日 01:53/ 0 赞/ 157 阅读

相关 HDU-1213-How Many Tables

链接：https://vjudge.net/problem/HDU-1213 题意：给n个人m个连通，求有几组思路：并查集模板代码：

女爷i/ 2021年12月24日 05:05/ 0 赞/ 215 阅读