10608 - Friends

[vahid sanei]

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

[mf]

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]

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);
}

[simon_cuet]

#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;
}

Code: Select all

[alamgir kabir]

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]

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]

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]

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

Please help me to find my Bug....

AC

[cse.mehedi]

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;
}

[brianfry713]

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;

[cse.mehedi]

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]

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

[cse.mehedi]

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]

Input:

Code: Select all

1
2 1
1 2

AC Output:

Code: Select all

2

[cse.mehedi]

TLE!!!!!