POJ-1213 How Many Tables (并查集模板题)

2017-01-13 19:14:08来源:CSDN作者:HHH_go_人点击

第七城市

点击查看原题
题目大意:一堆人开派对,只有认识的人才能坐一桌,问至少要几桌
并查集把认识的人链接起来,然后查找父亲一共有几个输出就是需要的桌子数量
AC代码

#include<stdio.h>#include<map>#include<string.h>using namespace std;int father[10000];int rank1[10000];void init(int n){    for(int i=0;i<=n;i++)    {        father[i]=i;        rank1[i]=0;    }}int find(int a){    return a==father[a]?a:find(father[a]);}bool unite(int a,int b){    a=find(a);    b=find(b);    if(a==b) return false;    if(rank1[a]<rank1[b])    {        father[a]=b;    }    else    {        father[b]=a;        if(rank1[a]==rank1[b])        {            rank1[a]++;        }    }}map<int,int>q;int main(){    int T;    scanf("%d",&T);    while(T--)    {        q.clear();        int n,m;        scanf("%d%d",&n,&m);        init(n);        for(int i=0;i<m;i++)        {            int a,b;            scanf("%d%d",&a,&b);            unite(a,b);        }        int ans=0;        for(int i=1;i<=n;i++)        {            if(!q[find(i)])            {                ans++;                q[find(i)]=1;            }        }        printf("%d/n",ans);    }}
第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台