本文主要是介绍hdu 1213 How Many Tables,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
主题思想 : union set 找联通分量。
union set 代码:
初始化:
//initfor(int i=1;i<=n;i++){a[i]=i;b[i]=1;}
int Find(int i){if(a[i]==i){return a[i];}a[i]=Find(a[i]);return a[i];
}void UN(int p,int q){p=Find(p);q=Find(q);if(p!=q){//num of p less num of qif(b[p]<b[q]){a[q]=a[p];b[p]=b[p]+b[q];}else{a[p]=a[q];b[q]+=b[p];}}return ;
}
AC代码:
#include <iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;const int maxn=1005;int a[maxn];
int b[maxn];int Find(int i){if(a[i]==i){return a[i];}a[i]=Find(a[i]);return a[i];
}void UN(int p,int q){p=Find(p);q=Find(q);if(p!=q){//num of p less num of qif(b[p]<b[q]){a[q]=a[p];b[p]=b[p]+b[q];}else{a[p]=a[q];b[q]+=b[p];}}return ;
}
int main()
{int T;scanf("%d",&T);int n,m;int p,q;while(T--){scanf("%d%d",&n,&m);//initfor(int i=1;i<=n;i++){a[i]=i;b[i]=1;}for(int i=0;i<m;i++){scanf("%d%d",&p,&q);UN(p,q);}int ans=0;for(int i=1;i<=n;i++){if(a[i]==i) ans++;}printf("%d\n",ans);}return 0;
}
这篇关于hdu 1213 How Many Tables的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!