当前位置: 代码迷 >> 综合 >> 数据结构 并查集
  详细解决方案

数据结构 并查集

热度:98   发布时间:2024-01-14 21:57:23.0

数小区

Time Limit: 1000MS Memory limit: 65536K

题目描述

某城市有n个人,现在给定关于n个人的m条信息,m条信息是两个人在同一个小区,根据所给信息,判断这个城市最多可能有多少个小区。n个人编号为1~n。

输入

多组输入。
每组第一行有两个整数n,m(2 <= n <= 50000, 0 <= m <= n/2)。
接下来m行,每行两个整数a,b,表示a和b在同一个小区。

输出

根据所给信息,输出这个城市最多可能有多少个小区。

示例输入

5 2
1 2
3 4

示例输出

3
#include<stdio.h>
int pre[51000];
int find(int x)
{
int r=x;
while(r!=pre[r])
{
r=pre[r];
}
int k=x;
int j;
while(k!=r)//路径压缩  非递归压缩;
{
j=pre[k];
pre[k]=r;
k=j;
}
return r;
}
void join(int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx!=fy)
pre[fx]=fy;
}
int main()
{
int m,n,i,j;
while(~scanf("%d%d",&n,&m))
{
for(i=0;i<=n;i++)
pre[i]=i;
int a,b;
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
join(a,b);
}
int count = 0;
for(i=1;i<=n;i++)
{
if(pre[i]==i)
count ++;
}
printf("%d\n",count);
}
}
#include<stdio.h>
int pre[51000];
int find(int x)//递归压缩路径
{
if(pre[x]!=x)
pre[x]=find(pre[x]);
return pre[x];
}
void join(int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx!=fy)
pre[fx]=fy;
}
int main()
{
int m,n,i,j;
while(~scanf("%d%d",&n,&m))
{
for(i=0;i<=n;i++)
pre[i]=i;
int a,b;
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
join(a,b);
}
int count = 0;
for(i=1;i<=n;i++)
{
if(pre[i]==i)
count ++;
}
printf("%d\n",count);
}
}