真的木有看出来是并查集。。差点就穷举了。。Orz大牛
保证 如果a,b在一个集合里 那么a和b+block，b和a+block肯定不在一个集合里，a+block和b+block在一个集合里。
如果a,b不在一个集合里 那么a和b+block，b和a+block肯定在一个集合里。
block是一个很大的数 起码要比单词的长度长，它的作用就是证明a,b在或者不在一个集合里。
对于a,b如果给的是even那么先判a，b是不是在一个集合里，不是不在的话（可能未知），union(a,b),union(a+block,b+block);
如果给的是odd那么先判a,b是不是不在一个集合里，不是在的话，union(a,b+block），union(a+block,b);
如果判的时候发生矛盾 直接退出 输出当前条序号。
#include<stdio.h>
long l,n,i,j,x,y,block;
long a[5001],b[5001];
char s[5001][6];
long f[100006];
long find(long a)
{
long i;
if (f[a]==a)
return a;
i=find(f[a]);
f[a]=i;
return i;
}
void uni(long a,long b)
{
long p,q;
p=find(a);
q=find(b);
if (q!=p)
f[q]=p;
}
int main()
{
block=50003;
while (scanf("%ld",&l)!=EOF)
{
if (l==-1)
return 0;
scanf("%ld",&n);
for (i=1;i<=n;i++)
{
scanf("%ld %ld %s",&a[i],&b[i],s[i]);
}
for (i=1;i<=block*2;i++)
{
f[i]=i;
}
f[0]=1;
for (i=1;i<=n;i++)
{
x=(a[i]-1)%block;y=b[i]%block;
if (s[i][0]=='e')
{
if (find(x)==find(y+block))
break;
uni(x,y);
uni(x+block,y+block);
}
else
{
if (find(x+block)==find(y+block))
break;
uni(x,y+block);
uni(x+block,y);
}
}
printf("%ld\n",i-1);
l=-1;
}
}
posted on 2011-06-27 16:44
梦转千寻 阅读(274)
评论(0) 编辑 收藏 引用