10608 - Friends

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

What`s different?

Post by vahid sanei » 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?
thanks in advance
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

Post by mf » 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.

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

Re:What`s different?

Post by vahid sanei » 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);
}
Impossible says I`m possible

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

Re: 10608 WA Why???

Post by simon_cuet » Wed Mar 11, 2009 10:38 am

#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

Post by alamgir kabir » Sun Apr 26, 2009 10:20 pm

I am getting WA. But I do not find any fault.
Please anybody help me

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.

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

Re: 10608 - Friends

Post by paradise_737 » 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[30100];
vector<int>Adjacency_List[31000];
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++ )
		dfs(Adjacency_List[x][i]);
	Adjacency_List[x].clear();
}
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;
				Adjacency_List[a].push_back(b);
				Adjacency_List[b].push_back(a);

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

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

Re: 10608

Post by suneast » Sun Mar 21, 2010 5:12 am

udvat wrote:dont use

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

instead use

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

Post by Eather » Wed Nov 16, 2011 8:36 pm

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

Please help me to find my Bug....
AC :)

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

10608 Why RE??

Post by cse.mehedi » 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

bool adj_mat[size][size],visited[size];

 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
        {
        adj_mat[size][size]={0},visited[size]={0};
        long arr[size]={0};
        while(con_no>=1)
        {
            scanf("%ld %ld",&a,&b);
            if(adj_mat[b][a]==0)
            adj_mat[a][b]=1;
            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++)
                    {
                        if(adj_mat[dequeue][j]==1)
                        {
                            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??

Post by brianfry713 » 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;
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??

Post by cse.mehedi » 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". :(

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

Re: 10608 Why RE??

Post by brianfry713 » 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
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??

Post by cse.mehedi » 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!

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

Re: 10608 Why RE??

Post by brianfry713 » Thu Apr 19, 2012 11:03 pm

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

Re: 10608 Why RE??

Post by cse.mehedi » Fri Apr 20, 2012 1:02 pm

TLE!!!!!

Post Reply

Return to “Volume 106 (10600-10699)”