## 10608 - Friends

Moderator: Board moderators

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### What`s different?

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?
Impossible says I`m possible

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10608 - Friends

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.

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### Re:What`s different?

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);
}``````
Impossible says I`m possible

simon_cuet
New poster
Posts: 2
Joined: Thu Feb 21, 2008 1:57 pm

### Re: 10608 WA Why???

#include<stdio.h>
long edge[30001][33],degree[500001],s=0,cc[30000]={0};

int dfs(long a[30000][33],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;
}

alamgir kabir
New poster
Posts: 37
Joined: Wed Oct 03, 2007 10:42 am

### Re: 10608 - Friends

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.

New poster
Posts: 5
Joined: Sun Aug 23, 2009 7:26 am

### Re: 10608 - Friends

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[30100];
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;
}
``````

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

### Re: 10608

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....: )

Eather
New poster
Posts: 28
Joined: Thu Jan 28, 2010 2:23 pm

### Re: 10608 - Friends

Oh, getting Wa. I use Disjoint set....

AC

cse.mehedi
New poster
Posts: 36
Joined: Sun Mar 18, 2012 8:18 am

### 10608 Why RE??

I can not understand why RE!

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[1]=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;
}

``````
Last edited by cse.mehedi on Fri May 25, 2012 2:09 pm, edited 6 times in total.

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

### Re: 10608 Why RE??

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;
Check input and AC output for thousands of problems on uDebug!

cse.mehedi
New poster
Posts: 36
Joined: Sun Mar 18, 2012 8:18 am

### Re: 10608 Why RE??

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".

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

### Re: 10608 Why RE??

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``````
Check input and AC output for thousands of problems on uDebug!

cse.mehedi
New poster
Posts: 36
Joined: Sun Mar 18, 2012 8:18 am

### Re: 10608 Why RE??

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!

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

### Re: 10608 Why RE??

Input:

Code: Select all

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

Code: Select all

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

cse.mehedi
New poster
Posts: 36
Joined: Sun Mar 18, 2012 8:18 am

TLE!!!!!