Page 4 of 6

### What`s different?

Posted: Tue Mar 03, 2009 9:10 am
Why this function for finding root gives me WA Code: Select all

``````int find_root(int n){
if(n==list[n].p)	return n;
find_root(list[n].p);
}
``````
and this`s correct

Code: Select all

``````int find_root(int n){
if(n!=list[n].p)
list[n].p=find_root(list[n].p);
return list[n].p;
}
``````
and what`s different between these two functions?

### Re: 10608 - Friends

Posted: Tue Mar 03, 2009 1:35 pm
Well, for one, the first version doesn't return a value in one of its two codepaths. A good compiler would have warned you about that.

### Re:What`s different?

Posted: Tue Mar 03, 2009 1:45 pm
thanks mf.
This works

Code: Select all

``````int find_root(int n){
if(n==list[n].p)   return n;
return find_root(list[n].p);
}``````

### Re: 10608 WA Why???

Posted: Wed Mar 11, 2009 10:38 am
#include<stdio.h>
long edge,degree,s=0,cc={0};

int dfs(long a,long start)
{
long i,y;
cc[start]=0;
s++;
for(i=1;i<=degree[start];i++)
{
y=edge[start];
if(cc[y]==1)
dfs(a,y);
}
return 0;

}

int main()
{
long n,m,i,j,v1,data,z=0,v2,test=0,start=1,x=0,count;
scanf("%ld",&data);
while(z++<data)
{
scanf("%ld%ld",&n,&m);
if(m==0)
{
printf("1\n");
}
else
{
for(i=1;i<=m;i++)
{
test=0;
scanf("%ld%ld",&v1,&v2);
if(cc[v1]==0)
{
degree[v1]=0;
cc[v1]=1;
}

if(cc[v2]==0)
{
degree[v2]=0;
cc[v2]=1;
}

for(j=1;j<=degree[v1];j++)
if(edge[v1][j]==v2)
{
test=1;
break;
}

if(test==0)
{
degree[v1]++;
edge[v1][degree[v1]]=v2;
}

test=0;

for(j=1;j<=degree[v2];j++)
if(edge[v2][j]==v1)
{
test=1;
break;
}

if(test==0)
{
degree[v2]++;
edge[v2][degree[v2]]=v1;
}

}
while(cc[start]==1)
{
x++;
dfs(edge,start);
if(x==1)
count=s;
if(x!=1)
if(count<s)
count=s;

s=0;
start=1;
for(i=1;i<=n;i++)
if(cc==1)
start=i;
}

printf("%ld\n",count);
x=0;
s=0;
start=1;
}
}

return 0;
}

### Re: 10608 - Friends

Posted: Sun Apr 26, 2009 10:20 pm
I am getting WA. But I do not find any fault.

Code: Select all

``````#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#define SIZE 50000

int rank [ SIZE ], parent [ SIZE ];

void init( int num )
{
for( int i = 0; i <= num; i ++ )
{
rank [ i ] = 0;
parent [ i ] = i;
}
return;
}

void create_set( int x )
{
parent [ x ] = x;
rank [ x ] = 0;
return;
}

int find_set( int x )
{
if( x == parent [ x ] ) return x;
else parent [ x ]  = find_set( parent [ x ]);
return  parent [ x ] ;
}

void marge_set( int x, int y )
{
int px, py;

px = find_set( x );
py = find_set( y );

if ( rank [ px ] > rank [ py ] ) parent [ py ] = px;
else if ( rank [ px ] < rank [ py ] ) parent [ px ] = py;
else if ( px != py ) parent [ py ] = px;

rank [ px ] = rank [ px ]  + 1;
return;
}

int main()
{
//freopen("input.txt", "r", stdin);
long test, n, m, i, a, b, set_a, set_b, max;
scanf("%ld", &test);
while( test -- )
{
scanf("%ld %ld", &n, &m);
init( n );
for( i = 0; i < m; i ++)
{
scanf("%ld %ld", &a, &b);
if( b == 0 )
{
printf("0\n");
continue;
}
set_a = find_set( a );
set_b = find_set( b );

if( set_a < 1 ) create_set( a );
if( set_a < 1 ) create_set( b );

if( set_a != set_b )marge_set( a, b );
//printf("s1 %ld r1 %ld s2 %ld r2 %ld\n", a, rank [ a ],  b, rank [ b ]);
}
for( i = 1; i <= n; i ++)
{
if( i == parent [ i ] )
{
rank [ i ]++;
}
else
{
rank [ parent [ i ] ] += rank [ i ];
}
//printf("rank %ld %ld\n", i, rank [ i ]);
}
for( i = 1, max = 0; i <= n; i ++)
{
if( max < rank [ i ] )
max = rank [ i ];
}
printf("%ld\n", max);
}
return 0;
}

``````
Thanx everybody.

### Re: 10608 - Friends

Posted: Tue Feb 23, 2010 2:35 am
hi guys ;
please can any body tell m why am getting WA or provide me with test cases different from those on board

Code: Select all

``````#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N , M;
bool Visited;
int a , b;
int Count;
int MAX;
void dfs( int x )
{
if( Visited[x] )
return;
Visited[x] = 1;
Count++;
for( int i = 0 ; i < Adjacency_List[x].size() ; i++ )
}
int main()
{
int Cases;
while( cin >> Cases )
{
for( int c = 0 ; c < Cases ; c++ )
{
MAX = 0;
cin >> N >> M;
memset(Visited,0,sizeof(Visited));
for( int i = 0 ; i < M ; i++ )
{
cin >> a >> b;

}
for( int i = 0 ; i <= N ; i++ )
if( !Visited[i] )
{
Count = 0;
dfs(i);
if( Count > MAX )
MAX = Count;
}
cout << MAX << endl;
}
}
return 0;
}
``````

### Re: 10608

Posted: Sun Mar 21, 2010 5:12 am
udvat wrote:dont use

while(scanf("%d",&test)==1)
{
while(test)
{
test--;
}
}

scanf("%d",&test);

while(test)
{
test--;
}

but thus u can escape from tle,but still your code holds a bug and getting WA.check it out.
Thankx udvat.

I finally got AC...

Maybe there is something wrong in the description....: )

### Re: 10608 - Friends

Posted: Wed Nov 16, 2011 8:36 pm
Oh, getting Wa. I use Disjoint set....

AC ### 10608 Why RE??

Posted: Tue Apr 17, 2012 4:08 pm
I can not understand why RE!
Please Any One Help Me! Code: Select all

``````
#include<stdio.h>
#define size 31000

main()
{

long n,node,con_no,a,b,i,dequeue,counter,tp,friends;
scanf("%ld",&n);
while(n--)
{
scanf("%ld %ld",&node,&con_no);
if(con_no==0)
printf("0\n");
else
{
long arr[size]={0};
while(con_no>=1)
{
scanf("%ld %ld",&a,&b);
con_no--;
}
friends=0;
for(int k=1;k<=node;k++)
{
i=1,arr=k,counter=1,tp=1;
while(1)
{
dequeue=arr[i];
if(dequeue==0) break;
if(visited[i]==0)
{
for(int j=1;j<=node;j++)
{
{
counter++;
visited[j]=1;
arr[tp++]=j;
}
}
visited[i]=0;
}
if(friends<counter) friends=counter;
i++;
}
}
printf("%ld\n",friends); }
}
return 0;
}

``````

### Re: 10608 Why RE??

Posted: Tue Apr 17, 2012 10:43 pm
if you declare a_mat of size c then you can only access up to c-1.

You're getting a seg fault during the sample input on line 16: a_mat[j]=0;

### Re: 10608 Why RE??

Posted: Tue Apr 17, 2012 10:53 pm
brianfry713 wrote:if you declare a_mat of size c then you can only access up to c-1.

You're getting a seg fault during the sample input on line 16: a_mat[j]=0;

I could not understand what should i do here "a_mat[j]=0". ### Re: 10608 Why RE??

Posted: Wed Apr 18, 2012 11:51 pm
You fixed the issue you were having before, trying to access beyond the limit of the array. Now I think you might be getting RE because you are trying put too much memory on the stack. Instead of declaring a huge local array long a_mat[c+1][c+1] where c can be up to 30000, and the values are only 0 or 1, try using a global bool array in c++.

This input causes your code to seg fault on my machine:

Code: Select all

``````1
30000 0``````

### Re: 10608 Why RE??

Posted: Thu Apr 19, 2012 7:56 pm
brianfry713 wrote:You fixed the issue you were having before, trying to access beyond the limit of the array. Now I think you might be getting RE because you are trying put too much memory on the stack. Instead of declaring a huge local array long a_mat[c+1][c+1] where c can be up to 30000, and the values are only 0 or 1, try using a global bool array in c++.

This input causes your code to seg fault on my machine:

Code: Select all

``````1
30000 0``````
Getting WA!

### Re: 10608 Why RE??

Posted: Thu Apr 19, 2012 11:03 pm
Input:

Code: Select all

``````1
2 1
1 2``````
AC Output:

Code: Select all

``2``

### Re: 10608 Why RE??

Posted: Fri Apr 20, 2012 1:02 pm
TLE!!!!!