Page 3 of 3
Posted: Thu Aug 12, 2004 5:10 pm
Oh sorry, I am dumb. I see now why your binary search works since you do not break when lo>=hi ^^;

i still don't see why your make_set works tho but maybe i will realize it latter : (

### Re: 10685 - Nature

Posted: Wed Sep 02, 2009 6:00 pm
i m getting frustrated on this problem,i got 8 WAs in this prob,i have passed all the I/Os on the board,pls help me.Advanced thanks to the helpers.

Code: Select all

``````#include<iostream>
#include<string>
#include<map>
using namespace std;

int p,rank,n,m,mx;
map<string,int>flag;

void ini()
{
int i;
for(i=0;i<=2*n+1;i++)
p[i]=i,rank[i]=0;
}

int find(int x)
{
if(x!=p[x])
p[x]=find(p[x]);
return p[x];
}
{
if(rank[x]>rank[y])
{
p[y]=x;
if(rank[y]>0) rank[x]+=rank[y];
else rank[x]++;
if(rank[x]>mx) mx=rank[x];
}
else if(rank[y]>rank[x])
{
p[x]=y;
if(rank[x]>0) rank[y]+=rank[x];
else rank[y]++;
if(rank[y]>mx) mx=rank[y];
}
else if(rank[x]==rank[y])
{

if(rank[x]==0)
{
p[y]=x;
rank[x]+=2;
if(rank[x]>mx) mx=rank[x];
}
else
{
p[y]=x;
if(rank[y]>0) rank[x]+=rank[y];
else rank[x]++;
if(rank[x]>mx) mx=rank[x];
}

}

}

int main()
{
int i,j,k,l,u,v;
char str1,str2;
while(scanf("%d%d",&n,&m) == 2)
{
if(n==0&&m==0) break;
flag.clear();
ini();
for(i=1;i<=n;i++)
{
scanf("%s",str1);
flag[str1]=i;
}
mx=0;
for(i=1;i<=m;i++)
{
scanf("%s%s",str1,str2);

u=find(flag[str1]);
v=find(flag[str2]);
if(u!=v)

}
if(mx==0)  mx++;

printf("%d\n",mx);

}

return 0;
}
``````

### Re: 10685 - Nature

Posted: Sun Oct 02, 2011 6:55 am
Jehad Uddin wrote:i m getting frustrated on this problem,i got 8 WAs in this prob,i have passed all the I/Os on the board,pls help me.Advanced thanks to the helpers.

Code: Select all

``````#include<iostream>
#include<string>
#include<map>
using namespace std;

int p,rank,n,m,mx;
map<string,int>flag;

void ini()
{
int i;
for(i=0;i<=2*n+1;i++)
p[i]=i,rank[i]=0;
}

int find(int x)
{
if(x!=p[x])
p[x]=find(p[x]);
return p[x];
}
{
if(rank[x]>rank[y])
{
p[y]=x;
if(rank[y]>0) rank[x]+=rank[y];
else rank[x]++;
if(rank[x]>mx) mx=rank[x];
}
else if(rank[y]>rank[x])
{
p[x]=y;
if(rank[x]>0) rank[y]+=rank[x];
else rank[y]++;
if(rank[y]>mx) mx=rank[y];
}
else if(rank[x]==rank[y])
{

if(rank[x]==0)
{
p[y]=x;
rank[x]+=2;
if(rank[x]>mx) mx=rank[x];
}
else
{
p[y]=x;
if(rank[y]>0) rank[x]+=rank[y];
else rank[x]++;
if(rank[x]>mx) mx=rank[x];
}

}

}

int main()
{
int i,j,k,l,u,v;
char str1,str2;
while(scanf("%d%d",&n,&m) == 2)
{
if(n==0&&m==0) break;
flag.clear();
ini();
for(i=1;i<=n;i++)
{
scanf("%s",str1);
flag[str1]=i;
}
mx=0;
for(i=1;i<=m;i++)
{
scanf("%s%s",str1,str2);

u=find(flag[str1]);
v=find(flag[str2]);
if(u!=v)

}
if(mx==0)  mx++;

printf("%d\n",mx);

}

return 0;
}
``````
If you haven't found out the problem yet, look at your stop condition, R can be 0 (or on your case, m).

Also, i would suggest changing the initialization of rank to 1 instead of 0, so you won't need that if(){}else{} on your link function.

### Re: 10685 - Nature

Posted: Sun Dec 21, 2014 6:59 pm
output of my accepted code for the given input:
1
3
4
2
9

### Re: 10685 - Nature

Posted: Thu Dec 25, 2014 4:58 pm
I've been getting WA with this code. I'm not really understanding where the bug lies. Can anyone please help me out?
[deleted the code as I got AC]

### Re: 10685 - Nature

Posted: Wed Jan 07, 2015 11:52 pm
Change line 22 to:
int PX = Find(x), PY = Find(y);

Change line 62 to:
for(i = 0; i<idx; i++){

### Re: 10685 - Nature

Posted: Fri Jan 09, 2015 1:42 am
Got AC. Thanks a ton ### Re: 10685 - Nature

Posted: Wed Feb 11, 2015 3:44 pm
Verdict: WA
can not get the problem..

Code: Select all

``````Remove After AC
``````

### Re: 10685 - Nature

Posted: Wed Feb 11, 2015 10:31 pm

### Re: 10685 - Nature

Posted: Sat Feb 14, 2015 2:33 pm
brianfry713 wrote:Don't read from a file.
Thanks brianfry

### Re: 10685 - Nature

Posted: Thu Apr 23, 2015 12:01 pm