10608 - Friends

[harry]

Using this algo i got A.C for 459 , 793 ,10227 . But why TLE for 10608
Can anyone help?
thanks in advance.

[udvat]

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.

[Ali Arman Tamal]

I'm getting W.A. Don't Know why .

I tested the program with a lot of inputs, and the answers were correct.

I will really appreciate some test cases...

I'm also posting my code:


// CUT



THANK YOU VERY MUCH !!!

[sohel]

It seems that you are using sets to divide the members into groups..
And the implementation of that is a little complicated and thus error prone.

.. but you can easily solve this problem using bfs/dfs.

[Ali Arman Tamal]

Thanks for your help Sohel.

But the problem is how should I represent the graph while using BFS of DFS.

Both the adjacency matrix and adjacency list representation may lead to a 30000*30000 memory requirements as there are 30000 vertexes (30000 people);

Thats why I used this method.

Give me a hint

PS: If anybody has solved this code, Please give me some TEST CASES.

THANK YOU VERY MUCH !!!

[sohel]

Both the adjacency matrix and adjacency list representation may lead to a 30000*30000 memory requirements as there are 30000 vertexes (30000 people);

Using Adjacency matrix will certainly get MLE/TLE, but the usage of adjacency list will suffice. There might be 30000 different vertices but there wont be cases where you have to handle 30000*30000 memory.

Remember there can be at most 500000 different pairs and that is not a lot.

You can use STL Vector to represent the matrix.. ( if you don't already know it) and then run a dfs.

Hope this will help you in some way.

[Adrian Kuegel]

Code: Select all

for(k=1;k<=n;k++)if(a[k]==a[j])a[k]=a[i];

this line is wrong. you should use a temporary variable for the value of a[j], since with this loop you are changing a[j] to a, so if there are values a[k] == a[j] with k>j, you will forget to set them to the new value a.
Btw, why didn't you use the union find data structure? It is much faster.

[Ali Arman Tamal]

I got Acc.

Thank you Adrian Kuegel, I was so blind !!!

[liang1425]

I've tried many datas,and it's correct......But I got W.A. >"<
Please help me!!Thanks a lot!!

Code: Select all

/*Q10608: Friends*/
/*2005.5.25   W.A.*/
#include<stdio.h>

int main()
{
    int i,j,n,a,b,c[30001],x,y,num,t[30001],max;
    
    scanf("%d",&n);
    while(n--){
        for(i=0;i<30001;i++){ c[i]=0; t[i]=0; }
        scanf("%d %d",&a,&b);
        num=0;
        while(b--){
           scanf("%d %d",&x,&y);
           if(c[x]){ 
               if(!c[y]){c[y]=c[x]; t[c[x]]++;}
               else if(c[x]!=c[y]){
                   t[c[x]]+=t[c[y]];
                   for(j=1;j<=a;j++)
                     if(c[j]==c[y]) c[j]=c[x];
               }
           }
           else{
              if(c[y]){ 
                  if(!c[x]){c[x]=c[y]; t[c[y]]++;}
                  else if(c[x]!=c[y]){
                      t[c[y]]+=t[c[x]]; 
                      for(j=1;j<=a;j++)
                          if(c[j]==c[x]) c[j]=c[y];
                  }
              }
              else{
                 num++;
                 c[x]=c[y]=num; t[num]=2;
              }
           }
        }
        max=0;
        for(i=1;i<=num;i++)
            if(t[i]>max) max=t[i];
        printf("%d\n",max);
    }

    return 0;
}

[Sedefcho]

Hi, liang1425 !

I've sent you a private message with your fixed code.

It will get ACC if you submit it.

Regards !

[liang1425]

Dear Sedefcho~
Thank you very much:)
I've known where my code was wrong.
Thank you.

[salamander]

I'm getting W.A. Don't Know why .

I post the code

Code: Select all

#include <cstdio>
#include <cstdlib>

int parent[30001];
int count[30001];

int main() {
    int t, m, n, a, b, Max;

    scanf("%d\n", &t);

    for (int i=0;i<t;i++) {
        scanf("%d %d\n", &m, &n);

        for (int j=1;j<=m;j++) {
            parent[j] = j;
            count[j] = 0;
        }

        for (int j=0;j<n;j++) {
            scanf("%d %d\n", &a, &b);

            while (parent[a] != a) {
                a = parent[a];
            }
            
            while (parent[b] != b) {
                b = parent[b];
            }

            if (a<b) {
                parent[b] = a;
            }
            else {
                parent[a] = b;
            }
        }

        for (int j=1;j<=m;j++) {
            count[parent[j]]++;
        }
        
        /*for (int j=1;j<=m;j++) {
			printf("%d ", count[j]);
		}
        putchar('\n');*/
        
        Max = 0;
       
        for (int j=1;j<=m;j++) {
            if (count[j] > Max) {
                Max = count[j];
            }
	    }

        printf("%d\n", Max);
    }
}

[salamander]

nobody know ?

[salamander]

Anyone know what wrong in my code???

[jdmetz]

You need to move all of b's friends to a's group or the other way, not just b or a:

Input:

Code: Select all

1
10 5
1 2
2 3
4 5
5 7
3 4

Output:

Code: Select all

6