数小区
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);
}
}