## 10685 - Nature

Moderator: Board moderators

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
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 : (

Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### Re: 10685 - Nature

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[10000],rank[10000],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[40],str2[40];
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;
}
``````

LucasSchm
New poster
Posts: 17
Joined: Mon May 18, 2009 10:00 pm

### Re: 10685 - Nature

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[10000],rank[10000],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[40],str2[40];
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.

sss
New poster
Posts: 1
Joined: Tue Feb 26, 2013 8:23 pm

### Re: 10685 - Nature

output of my accepted code for the given input:
1
3
4
2
9

Tahanima
New poster
Posts: 8
Joined: Thu Dec 25, 2014 4:50 pm

### Re: 10685 - Nature

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]
Last edited by Tahanima on Fri Jan 09, 2015 1:51 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10685 - Nature

Change line 22 to:
int PX = Find(x), PY = Find(y);

Change line 62 to:
for(i = 0; i<idx; i++){
Check input and AC output for thousands of problems on uDebug!

Tahanima
New poster
Posts: 8
Joined: Thu Dec 25, 2014 4:50 pm

### Re: 10685 - Nature

Got AC. Thanks a ton

Tanmoy1228
New poster
Posts: 10
Joined: Sat Jul 19, 2014 2:55 am

### Re: 10685 - Nature

Verdict: WA
can not get the problem..

Code: Select all

``````Remove After AC
``````
Last edited by Tanmoy1228 on Sat Feb 14, 2015 2:32 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10685 - Nature

Check input and AC output for thousands of problems on uDebug!

Tanmoy1228
New poster
Posts: 10
Joined: Sat Jul 19, 2014 2:55 am

### Re: 10685 - Nature

brianfry713 wrote:Don't read from a file.
Thanks brianfry

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 10685 - Nature

http://www.udebug.com/UVa/10685
Check input and AC output for over 7,500 problems on uDebug!