| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:没有啊In Reply To:没有啊 Posted by:zdker at 2005-10-05 10:14:55 能帮我看看我的程序吗,我觉得我的想法应该没什么漏洞啊,
#include "stdio.h"
#include "memory.h"
int s[100010]={0},root[100010]={0};//s中保存与下标不在同一个集合的数
int fd(int n)
{
if(root[n]==0) { root[n]=n;return n;}
int i=n;
while(i!=root[i])
root[i]=root[root[i]],i=root[i];
root[n]=i;
return i;
}
int nn(int i,int j)
{
int a1,a2;
a1=fd(i),a2=fd(j);
if(a1<a2) { root[i]=a1,root[j]=a1;}
else { root[i]=a2,root[j]=a2;}
return 0;
}
int main(void)
{
int cs,n,m,i,j,a,b;
char ch;
scanf("%d",&cs);
while(cs>0){
cs--;
memset(s,0,sizeof(s));
memset(root,0,sizeof(root));
scanf("%d%d",&n,&m);
for(i=0;i<n;i++){
gets(&ch);
scanf("%c",&ch);
scanf("%d%d",&a,&b);
if(ch=='D'){
if(s[a]==0)
s[a]=b;
else
nn(s[a],b);
if(s[b]==0)
s[b]=a;
else
nn(a,s[b]);
}
else
{
if(fd(a)==fd(b))
printf("In the same gang.\n");
else
if(s[a]&&fd(s[a])==fd(b)||s[b]&&fd(s[b])==fd(a))
printf("In different gangs.\n");
else
printf("Not sure yet.\n");
}
}
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator