| ||||||||||
| 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:用并查集做的 Why wrong?期待高手指点In Reply To:用并查集做的 Why wrong?期待高手指点 Posted by:newton88518 at 2006-11-12 13:07:04 > #include<stdio.h>
> #include<string.h>
> #include<math.h>
> #include<stdlib.h>
> #define N 6000001
> int v[N],d[N],n;
> int findd(int p)
> {
> int i;
> for(i=p;i!=v[i];i=v[i])
> v[i]=v[v[i]];
> return i;
> }
> void linkp(int pa,int pb)
> {
> pa=findd(pa);
> pb=findd(pb);
> if(pa==pb) return;
> if(d[pa]>d[pb])
> {
> v[pb]=pa;
> d[pa]+=d[pb];
> }
> else
> {
> v[pa]=pb;
> d[pb]+=d[pa];
> }
> }
> int suma,sumb;
> bool judge(int pa,int pb)
> {
> pa=findd(pa);
> pb=findd(pb);
> if(pa==pb) {
> suma++;
> return 1;
> }
> sumb++;
> return 0;
> }
> void init()
> {
> int i;
> for(i=1;i<=n;i++)
> {
> v[i]=i;
> d[i]=1;
> }
> }
> int main()
> {
> //freopen("a.in","r",stdin);
> char s[300],g[10];
> int r[5],k=0,i;
>
> while(gets(s))
> {
> k=0;
> i=1;
> while(sscanf(s+i,"%s",g)!=EOF)
> {
> do ++i;
> while(s[i]==' ');
> i+=strlen(g);
> r[k]=atoi(g);
> // printf("%d ",r[k]);
> k++;
> }
> // printf("\n");
> if(s[0]=='c' || s[0]=='C')
> {
> if(k==2) linkp(r[0],r[1]);
> else if(k==3)
> {
> for(i=0;i<r[2];i++)
> linkp(r[0],r[1]+i);
> }
> else if(k==4)
> {
> if(r[3]==0) linkp(r[0],r[1]);
> else
> for(i=0;i<r[2];i++)
> {
> linkp(r[0],r[1]);
> r[1]+=r[3];
> }
> }
> else
> {
> if(r[3]==0 && r[4]==0) linkp(r[0],r[1]);
> else
> for(i=0;i<r[2];i++)
> {
> linkp(r[0],r[1]);
> r[0]+=r[4];
> r[1]+=r[3];
> }
> }
> }
> else if(s[0]=='q' || s[0]=='Q')
> {
> suma=sumb=0;
> if(k==2) judge(r[0],r[1]);
> else if(k==3)
> {
> for(i=0;i<r[2];i++)
> judge(r[0],r[1]+i);
> }
> else if(k==4)
> {
> if(r[3]==0) judge(r[0],r[1]);
> else
> for(i=0;i<r[2];i++)
> {
> judge(r[0],r[1]);
> r[1]+=r[3];
> }
> }
> else
> {
> if(r[3]==0 && r[4]==0) judge(r[0],r[1]);
> else
> for(i=0;i<r[2];i++)
> {
> judge(r[0],r[1]);
> r[0]+=r[4];
> r[1]+=r[3];
> }
> }
> printf("%d - %d\n",suma,sumb);
> }
> else
> {
> n=r[0];
> init();
> }
> }
> return 0;
> }
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator