23——poj 1611/ hdoj 4496

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4496

并查集删除边的操作


//并查集删除边,正常情况下我们遇到的都是并查集添加边,其实这题就是逆向思维
//题目给的是完全图,先把各点与边的关系存储下来,然后倒过来,加边
//用并查集查找每两个点是否是联通的,若不是,则-1,把两点合并,否则不变

#include<iostream>
#include<malloc.h>
using namespace std;
#define N 100000+5
int father[N];
int n;
struct node //定义结构体存储各边
{
int x;
int y;
};
int find(int x)
{
if(x!=father[x])
father[x]!=find(father[x]);
return father[x];
}
void initialize()
{
for(int i=1;i<=n;i++)
{
father[i]=i;
}
}
struct node point[N];
int main()
{
int m,a,b;
int num[N];
while(cin>>n>>m)
{
initialize();
num[m]=n; //最大的就是n
for(int i=1;i<=m;i++)
cin>>point[i].x>>point[i].y;
for(int i=m;i>1;i--)
{
a=find(point[i].x);
b=find(point[i].y);
if(a!=b)
{
num[i-1]=num[i]-1;
father[a]=b;
}
else
num[i-1]=num[i];
}
for(int i=1;i<=m;i++)
cout<<num[i]<<endl;
}
return 0;
}


题目链接: http://poj.org/problem?id=1611

统计集合元素的个数

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define N 30000+5
int father[N],num[N],rank[N];
int n;
void initialize() //初始化
{
int i;
for(i=0;i<n;i++)
{
father[i]=i; //把所有根节点设为本身
num[i]=1; //初始时各集合元素个数为1
rank[i]=0;
}
}
int find(int x) //查找,路径压缩,递归
{
if(x!=father[x])
father[x]=find(father[x]);
return father[x];
}

void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
return;
if(rank[x]>rank[y]) //按秩合并
{
father[y]=x;
num[x]+=num[y]; //将集合数进行合并
}
else
{
father[x]=y;
num[y]+=num[x];
}
}
int main()
{
int m,x,y,t;
while(~scanf("%d%d",&n,&m))
{
if(n==0&&m==0)
break;
initialize();
while(m--)
{
cin>>t;
cin>>x; //为了进行合并,先输入一个x
for(int i=1;i<t;i++) //接下来从1开始,两两合并
{
cin>>y;
unite(x,y);
x=y;
}
}
cout<<num[find(0)]<<endl;//找到0的根节点所在的集合,并输出集合中的元素
}
return 0;
}



评论

© 现实给了梦想多少时间 | Powered by LOFTER