poj 1182

http://poj.org/problem?id=1182

一个利用并查集的经典题目。

思路:在网上看到别人的思路,觉得方法还是挺不错的。

首先,开辟一个3*n的数组belg,用来存b和c的关系,在belg[c+m]存,c是被谁吃的,belg[c+2*m]存b是吃谁的。

bool judge(int x,int y) {return (Find(x)==Find(y));}

如果judge(b,c+m)和 judge(b,c+2*m)都为假的话,那么可以说明,b和c是在同类。

然后合并b,c。b+m,c+m。b+2m,c+2m。

第一个judge可以判断,b不会吃c,第二个Judge可以判断c也不会吃b,所以,b,c肯定是同类。

如果judge(b,c)和judge(b,c+2*m)都为假的话,那么可以说明,c是被b吃的,然后合并b,c+m。b+m,c+2*m。b+*2m,c;

第一个judge可以判断b和c不是同一类,第二个judge可以判断c不会吃b,那么就可以说明c是被b吃的。c是被b吃的,那么说明,c+m存的就是b,所以c+m和b合并。之后的也是同样的意思。

 #include <stdio.h>
#include <string.h> int belg[]; int Find(int x) //Find 的迭代写法。
{
int _x=x,_b;
while(_x!=belg[_x])
{
_x=belg[_x];
}
while(x!=belg[x])
{
_b=belg[x];
belg[x]=_x;
x=_b;
}
return _x;
} bool judge(int x,int y) {return (Find(x)==Find(y));} void unite(int x,int y)
{
int root1=Find(x);
int root2=Find(y);
if(root1!=root2) belg[root1]=root2;
} int main()
{
int m,n,a,b,c,ans=;
// freopen("in.txt","r",stdin);
scanf("%d%d",&m,&n);
for(int i=;i<=m*;i++)
belg[i]=i;
while(n--)
{
scanf("%d%d%d",&a,&b,&c);
if(b>m||c>m) ans++;
else if(a==)
{
if(judge(b,c+m)||judge(b,c+*m)) ans++;
else { //b,c是同类时,合并所有的信息。
unite(b,c);
unite(b+m,c+m);
unite(b+*m,c+*m);
}
}
else {
if(judge(b,c)||judge(b,c+*m)) ans++;
else { //b,c不是同类时,合并那些是同类的信息。
unite(b,c+m);
unite(b+m,c+*m);
unite(b+*m,c);
}
}
}
printf("%d\n",ans);
return ;
}
上一篇:【译文】用Spring Cloud和Docker搭建微服务平台


下一篇:从 Spring Cloud 看一个微服务框架的「五脏六腑」(转)