1)hdoj1232:畅通工程
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1232
简单并查集
#include <iostream>
#include <vector>
#include <string.h>
#include <cmath>
#include <algorithm>
#define maxn 1010
using namespace std;
int father[maxn];
bool isboot[maxn];
int findfather(int x)
{
while(x!=father[x])
x=father[x];
return x;
}
void Union(int a,int b)
{
int A=findfather(a),B=findfather(b);
if(A!=B)
father[A]=B;
}
int main()
{
int n,m,i,j,a,b;
while(cin>>n && n!=0)
{
cin>>m;
int ans=0;
for(i=1;i<=n;i++)
{
father[i] = i;
isboot[i] = false;
}
for(i=0;i<m;i++)
{
cin>>a>>b;
Union(a,b);
}
for(i=1;i<=n;i++)
{
isboot[findfather(i)]=true;
ans+=isboot[i];
}
cout<<ans-1<<endl;
}
return 0;
}
2)hdoj1272:小希的迷宫
题解:https://blog.csdn.net/Cassie_zkq/article/details/86525812
注意坑点
3)hdoj1213:How Many Tables
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1213
赤裸裸的并查集
#include <iostream>
#include <vector>
#include <string.h>
#include <cmath>
#include <algorithm>
#define maxn 1005
using namespace std;
int father[maxn];
int findfather(int x)
{
while(x!=father[x])
x=father[x];
return x;
}
void Union(int n,int m)
{
int N=findfather(n);
int M=findfather(m);
if(N!=M)
father[N]=M;
}
int main()
{
int t,n,m,a,b,i;
scanf("%d",&t);
while(t--)
{
int ans=0;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
father[i]=i;
for(i=1;i<=m;i++)
{
scanf("%d %d",&a,&b);
Union(a,b);
}
for(i=1;i<=n;i++)
if(father[i]==i)
ans++;
cout<<ans<<endl;
}
return 0;
}